题目链接：http://www.spoj.com/problems/IITWPC4F/
————————————————————————————-.
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
————————————————————————————-.
题目大意：
就是有一个横纵坐标范围均为
定义三种操作,
x a b 将x轴坐标范围
y a b 将y轴坐标范围
解题思路:
因为题目提示的是整行的操作,所以很容易想到用两个数组分别标记对应行/列的翻转次数,奇数次为1,偶数次为0.
然后因为动态求区间和,想到树状数组,
然后发现一点,树状数组虽然能够很好的维护某一个值增减的变化,但是对于区间内翻转的变化既有增也有减,所以不可行,于是换成麻烦写的线段树维护就好了,
用区间更新就能很好的维护翻转标记了.
然后查询的操作与二维树状数组求和的操作一模一样,不再赘述.
附本题代码
——————————————————————————-.
#include <bits/stdc++.h>
using namespace std;
const int N = 100000+5;
typedef long long int LL;
/***************************************/
struct node {
int l,r;
LL val;
int lazy;
int md(){return (l+r)>>1; }
int ln(){return (r-l+1); }
}tree[N<<2][2];
#define ll (rt<<1)
#define rr (rt<<1|1)
#define mid (tree[rt][xy].md())
void pushup(int rt,int xy){
tree[rt][xy].val = tree[ll][xy].val+ tree[rr][xy].val;
}
void build(int rt,int l,int r,int xy){
tree[rt][xy].l=l,tree[rt][xy].r=r;
tree[rt][xy].val=0ll,tree[rt][xy].lazy=0;
if(l==r) return ;
build(ll,l,mid,xy);
build(rr,mid+1,r,xy);
}
void pushdown(int rt,int xy){
if(tree[rt][xy].lazy){
tree[rr][xy].lazy = 1 - tree[rr][xy].lazy;
tree[ll][xy].lazy = 1 - tree[ll][xy].lazy;
tree[ll][xy].val = tree[ll][xy].ln()-tree[ll][xy].val;
tree[rr][xy].val = tree[rr][xy].ln()-tree[rr][xy].val;
tree[rt][xy].lazy = 0;
}
}
void update(int rt,int L,int R,int xy){
if(L<=tree[rt][xy].l&&tree[rt][xy].r<=R){
tree[rt][xy].lazy = 1-tree[rt][xy].lazy;
tree[rt][xy].val = tree[rt][xy].ln()-tree[rt][xy].val;
return ;
}
pushdown(rt,xy);
if(L<=mid) update(ll,L,R,xy);
if(R> mid) update(rr,xy);
pushup(rt,xy);
}
LL query(int rt,int xy){
if(L<=tree[rt][xy].l&&tree[rt][xy].r<=R){
return tree[rt][xy].val ;
}
pushdown(rt,xy);
LL ans = 0;
if(L<=mid) ans+=query(ll,xy);
if(R> mid) ans+=query(rr,xy);
return ans;
}
LL getSum(int x,int y){
//if(0>=x||0>=y) return 0ll;
LL X=query(1,0,x,1),Y=query(1,y,0);
return 1ll*X*(y-Y)+1ll*Y*(x-X);
}
int main(){
int n,x1,x2,y1,y2;
char ch ;
build(1,100001,0);
build(1,1);
scanf("%d",&n);getchar();
for(int i=0;i<n;i++){
scanf("%c ",&ch);
if('x'==ch){
scanf("%d %d",&x,&y);
x++,y++;
update(1,1);
}
else if('y'==ch){
scanf("%d %d",0);
}
else {
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++,x2++,y1++,y2++;
printf("%lld\n",getSum(x2,y2)-getSum(x1-1,y2)-getSum(x2,y1-1)+getSum(x1-1,y1-1));
}
getchar();
}
return 0;
}
/** 树状数组维护x，y的区间 tree[rt][1] XXXXXXXX tree[rt][0] YYYYYYYY */
