首页 > 代码库 > spoj IITWPC4F - Gopu and the Grid Problem 线段树

spoj IITWPC4F - Gopu and the Grid Problem 线段树

IITWPC4F - Gopu and the Grid Problem

no tags 

 

Gopu is interested in the integer co-ordinates of the X-Y plane (0<=x,y<=100000). Each integer coordinate contain a lamp, initially all the lamps are in off mode. Flipping a lamp means switching it on if it is in off mode and vice versa. Maggu will ask gopu 3 type of queries.

 

 

Type 1:  x l r,  meaning: flip all the lamps whose x-coordinate are between l and r (both inclusive) irrespective of the y coordinate.

 

 

Type 2:  y l r, meaning: flip all the lamps whose y-coordinate are between l and r (both inclusive) irrespective of the x coordinate.

 

 

Type 3: q x y X Y, meaning: count the number of lamps which are in ‘on mode’(say this number be A) and ‘off mode’ (say this number  be B) in the region where x-coordinate is between x and X(both inclusive) and y-coordinate is between y and Y(both inclusive).

Input

First line contains Q-number of queries that maggu will ask to gopu. (Q <= 10^5)

 

Then there will be Q lines each containing a query of one of the three type described above.

Output

For each query of 3rd type you need to output a line containing one integer A.

Example

Input:

3

x 0 1

y 1 2

q 0 0 2 2

Output: 
 4

线段树

题目链接:http://www.spoj.com/problems/IITWPC4F/en/

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define mk make_pair#define eps 1e-7#define bug(x)  cout<<"bug"<<x<<endl;const int N=5e5+10,M=1e6+10,inf=2147483647;const ll INF=1e18+10,mod=1000000007;///   数组大小struct SGT{    int tree[N],lazy[N];    void pushup(int pos)    {        tree[pos]=tree[pos<<1|1]+tree[pos<<1];    }    void pushdown(int pos,int l,int r)    {        if(lazy[pos])        {            lazy[pos<<1]^=1;            lazy[pos<<1|1]^=1;            int mid=(l+r)>>1;            tree[pos<<1]=(mid-l+1)-tree[pos<<1];            tree[pos<<1|1]=(r-mid)-tree[pos<<1|1];            lazy[pos]=0;        }    }    void build(int l,int r,int pos)    {        tree[pos]=lazy[pos]=0;        if(l==r)return;        int mid=(l+r)>>1;        build(l,mid,pos<<1);        build(mid+1,r,pos<<1|1);    }    void update(int L,int R,int l,int r,int pos)    {        if(L<=l&&r<=R)        {            lazy[pos]^=1;            tree[pos]=(r-l+1)-tree[pos];            return;        }        pushdown(pos,l,r);        int mid=(l+r)>>1;        if(L<=mid)            update(L,R,l,mid,pos<<1);        if(R>mid)            update(L,R,mid+1,r,pos<<1|1);        pushup(pos);    }    int query(int L,int R,int l,int r,int pos)    {        if(L<=l&&r<=R)            return tree[pos];        pushdown(pos,l,r);        int mid=(l+r)>>1;        int ans=0;        if(L<=mid)            ans+=query(L,R,l,mid,pos<<1);        if(R>mid)            ans+=query(L,R,mid+1,r,pos<<1|1);        return ans;    }};SGT x,y;char ch[10];int main(){    int q;    int n=100010;    while(~scanf("%d",&q))    {        x.build(1,n,1);        y.build(1,n,1);        while(q--)        {            int l,r;            scanf("%s%d%d",ch,&l,&r);            //if(l<r)swap(l,r);            if(ch[0]==x)                x.update(l+1,r+1,1,n,1);            else if(ch[0]==y)                y.update(l+1,r+1,1,n,1);            else            {                int L,R;                scanf("%d%d",&L,&R);                //if(L<R)swap(L,R);                int xx=x.query(l+1,L+1,1,n,1);                int yy=y.query(r+1,R+1,1,n,1);                ll ans=0;                ans+=1LL*xx*(R-r+1);                ans+=1LL*yy*(L-l+1);                ans-=2LL*xx*yy;                printf("%lld\n",ans);            }        }    }    return 0;}

 

spoj IITWPC4F - Gopu and the Grid Problem 线段树