implicit segment tree

problem : http://codeforces.com/problemset/problem/555/C
code from : http://codeforces.com/problemset/submission/555/38210662
#include<bits/stdc++.h>
using namespace std;

#define si(n) scanf("%d",&n)

struct Node{
    int m;
    Node *l,*r;
    Node(){m=0;l=NULL;r=NULL;}
};

void update(Node *root,int tl,int tr,int l,int r,int val)
{
    if(l>r || r<tl || l>tr)return;

    if(tl>=l && tr<=r){
        root->m=max(root->m,val);
        return ;
    }
    int mid=(tl+tr)/2;
    if(root->l==NULL)root->l=new Node();
    if(root->r==NULL)root->r=new Node();
    update(root->l,tl,mid,l,r,val);
    update(root->r,mid+1,tr,l,r,val);
}

int get(Node *root,int tl,int tr,int pos)
{
    if(root==NULL || tl>tr || pos<tl || pos>tr)
        return 0;
    if(tl==tr)return root->m;
    int mid=(tl+tr)/2;
    return max(root->m,max(get(root->l,tl,mid,pos),
                           get(root->r,mid+1,tr,pos)));
}

Node *tv,*th;


int main()
{
    //freopen("input.txt","r",stdin);
    int i,j,n,q;
    si(n);si(q);
    tv=new Node();
    th=new Node();
    while(q--){
        int x,y,z;
        char ch;
        si(y);si(x);scanf(" %c",&ch);

        if(ch=='U'){
            z=get(tv,1,n,y);
            //cout<<z<<endl;
            printf("%d\n",x-z);
            update(tv,1,n,y,y,x);
            update(th,1,n,z,x,y);
        }
        else{
            z=get(th,1,n,x);
            printf("%d\n",y-z);
            update(th,1,n,x,x,y);
            update(tv,1,n,z,y,x);
        }
    }
}