HackerRank: Quadrant Queries ( Segment Tree )

HackerRank: Quadrant Queries ( Segment Tree )

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     100002
#define inf    2000000010
#define MD     1000000000LL
#define eps    1e-9
///===============================///

struct data {
    int a[4];
    data() {};
};
data nd[(4*MX)+2];
int mk[(4*MX)+2],ans[4],tmp[5];
pii pp[MX+2];

int go(int i) {
    int m=0;
    if(pp[i].X<0)m|=2; ///for neg X -1th bit ON;
    if(pp[i].Y<0)m|=1; ///for neg Y -0th bit ON;
    return m;
}

void Build(int id,int l,int r) {
    mk[id]=0;
    if(l==r) {
        nd[id].a[ go(l) ]=1;
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    Build(lft,l,md);
    Build(rgt,md+1,r);
    fr(i,0,3)nd[id].a[i]=(nd[lft].a[i]+nd[rgt].a[i]);
}

void Upd(int id,int l,int r,int q1,int q2,int m) {
    if( l==q1 && r==q2 ) {
        fr(i,0,3)tmp[i]=nd[id].a[i];
        fr(i,0,3)nd[id].a[i]=tmp[ i^m ];
        mk[ id ]^=m;
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( mk[id] ) {
        int mm=mk[id];
        fr(i,0,3)tmp[i]=nd[lft].a[i];
        fr(i,0,3)nd[lft].a[i]=tmp[ i^mm ];

        fr(i,0,3)tmp[i]=nd[rgt].a[i];
        fr(i,0,3)nd[rgt].a[i]=tmp[ i^mm ];

        mk[ lft ]^=mm,mk[ rgt ]^=mm;
        mk[id]=0;
    }
    if(q2<=md) Upd(lft,l,md,q1,q2,m);
    else if(q1>md) Upd(rgt,md+1,r,q1,q2,m);
    else {
        Upd(lft,l,md,q1,md,m);
        Upd(rgt,md+1,r,md+1,q2,m);
    }
    fr(i,0,3)nd[id].a[i]=(nd[lft].a[i]+nd[rgt].a[i]);
}

data Qry(int id,int l,int r,int q1,int q2) {
    if( l==q1 && r==q2 ) return nd[id];
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( mk[id] ) {
        int mm=mk[id];
        fr(i,0,3)tmp[i]=nd[lft].a[i];
        fr(i,0,3)nd[lft].a[i]=tmp[ i^mm ];

        fr(i,0,3)tmp[i]=nd[rgt].a[i];
        fr(i,0,3)nd[rgt].a[i]=tmp[ i^mm ];

        mk[ lft ]^=mm,mk[ rgt ]^=mm;
        mk[id]=0;
    }
    if(q2<=md) return Qry(lft,l,md,q1,q2);
    else if(q1>md) return Qry(rgt,md+1,r,q1,q2);
    else {
        data x=Qry(lft,l,md,q1,md);
        data y=Qry(rgt,md+1,r,md+1,q2);
        data ret;
        fr(i,0,3)ret.a[i]=(x.a[i]+y.a[i]);
        return ret;
    }
}

int main() {
    int tc,cs=1,i,j,k,n,x,y,q;
    //S(tc);
    tc=1;
    while(tc--) {
        S(n);
        CLR(nd);
        fr(i,1,n) {
            S2(pp[i].X,pp[i].Y);
        }
        Build(1,1,n);
        S(q);
        while(q--) {
            char ch[2];
            scanf("%s",ch);
            S2(x,y);
            if(ch[0]=='X') {
                Upd(1,1,n,x,y,1);
            } else if(ch[0]=='Y') {
                Upd(1,1,n,x,y,2);
            } else {
                data dt=Qry(1,1,n,x,y);
                printf("%d %d %d %d\n",dt.a[0],dt.a[2],dt.a[3],dt.a[1]);
            }
        }
    }
    return 0;
}