SPOJ IITWPC4F - Gopu and the Grid Problem [线段树]【数据结构
|
题目链接：http://www.spoj.com/problems/IITWPC4F/ 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). 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. For each query of 3rd type you need to output a line containing one integer A. Example Input: Output: 解题思路: 然后因为动态求区间和,想到树状数组, 然后发现一点,树状数组虽然能够很好的维护某一个值增减的变化,但是对于区间内翻转的变化既有增也有减,所以不可行,于是换成麻烦写的线段树维护就好了, 用区间更新就能很好的维护翻转标记了. 然后查询的操作与二维树状数组求和的操作一模一样,不再赘述. 附本题代码 #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("%lldn",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 */
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |