题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1230
分析:
在每个节点打标记,打完标记要反转当前节点灯。这个点打上标记表示下面子节点灯还没有反转,然而这个点的灯是反转的。
所以每次要先标记下标记下放,然后开始更新此节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; bool visit[400010]; int sum[400010]; void change_mean(int x,int l,int r) { sum[x]=r-l+1-sum[x]; return ; } void pushdown(int x,int l,int r) { if(visit[x]) { visit[x]=false; int mid=(l+r)>>1; change_mean(x<<1,l,mid); change_mean(x<<1|1,mid+1,r); visit[x<<1]^=1; visit[x<<1|1]^=1; } return ; } void change_tree(int step,int l,int r,int xx,int yy) { pushdown(step,l,r); if(xx<=l&&yy>=r) { visit[step]=true; change_mean(step,l,r); return ; } int mid=(l+r)>>1; if(xx>=mid+1) { change_tree(step<<1|1,mid+1,r,xx,yy); } else if(yy<=mid) { change_tree(step<<1,l,mid,xx,yy); } else { change_tree(step<<1,l,mid,xx,yy); change_tree(step<<1|1,mid+1,r,xx,yy); } sum[step]=sum[step<<1]+sum[step<<1|1]; return ; } int puery_tree(int step,int l,int r,int xx,int yy) { if(xx<=l&&yy>=r) { return sum[step]; } pushdown(step,l,r); int mid=(l+r)>>1; if(xx>=mid+1) { return puery_tree(step<<1|1,mid+1,r,xx,yy); } else if(yy<=mid) { return puery_tree(step<<1,l,mid,xx,yy); } else { return puery_tree(step<<1,l,mid,xx,yy)+puery_tree(step<<1|1,mid+1,r,xx,yy); } } int main() { int type,x1,y1; scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { scanf("%d%d%d",&type,&x1,&y1); if(!type) { change_tree(1,1,n,x1,y1); } else { printf("%d\n",puery_tree(1,1,n,x1,y1)); } } return 0; } |