SPOJ IITWPC4F - Gopu and the Grid Problem （双线段树区间修改 区间查询）

Gopu and the Grid Problem

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
一开始想的是直接二维线段树或者二维树状数组搞一下，然后一看数据范围，GG。实在没办法看了网上的题解，用两个线段树分别处理行和列，然后查询的时候，再综合一下。
减去重叠的部分。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 1e5+;
const int M = ;
typedef long long LL;

int q;
struct Seg {
    int Tree[N << ]; // 标记的行数/列数
    bool lazy[N << ];
    void init() {
        memset(Tree, , sizeof(Tree));
        memset(lazy, , sizeof(lazy));
    }
    inline void pushup(int rt) { Tree[rt] = Tree[rt << ] + Tree[rt <<  | ]; }
    inline void pushdown(int pos,int len)
    {
        if(lazy[pos])
        {
            Tree[pos<<]=len-len/-Tree[pos<<];
            Tree[pos<<|]=len/-Tree[pos<<|];
            lazy[pos<<]^=;
            lazy[pos<<|]^=;
            lazy[pos]=;
        }
        return;
    }
    void update(int L,int R,int l,int r,int pos)
    {
        if(l>=L&&r<=R)
        {
            Tree[pos]=(r-l+)-Tree[pos];
            lazy[pos]^=;
            return;
        }
        int mid=(l+r)>>;
        pushdown(pos,r-l+);
        if(L<=mid) update(L,R,l,mid,pos<<);
        if(mid<R)update(L,R,mid+,r,pos<<|);
        pushup(pos);
    }
    int query(int L,int R,int l,int r,int pos)
    {
        if(L<=l&&r<=R)return Tree[pos];
        int mid=(l+r)>>;
        pushdown(pos,r-l+);
        int ans=;
        if(L<=mid) ans+=query(L,R,l,mid,pos<<);
        if(R>mid) ans+=query(L,R,mid+,r,pos<<|);
        return ans;
    }
}row,col;

int main() {
    char op[];
    int n = N;
    row.init();
    col.init();
    int l,r,val;
    int lx,ly,rx,ry;
    char sign[];
    int m;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",sign);
        if(sign[]=='x')
        {
            scanf("%d%d",&l,&r);
            ++l,++r;
            row.update(l,r,,n,);
        }
        else if(sign[]=='y'){
            scanf("%d%d",&l,&r);
            ++l,++r;
            col.update(l,r,,n,);
        }
        else
        {
            scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
            ++lx,++ly,++rx,++ry;
            int nx=row.query(lx,rx,,n,);
            int ny=col.query(ly,ry,,n,);
            ll ans=(ll)(rx-lx+)*ny+(ll)(ry-ly+)*nx-(ll)*nx*ny;
            printf("%lld\n",ans);
        }
    }
}