SPOJ MULTQ3

/*sum[root][i]表示root节点的子叶子%3余i的总数
　lazy懒惰标记
*/



 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 #define N 400010
 5 int sum[N][3],lazy[N];
 6 void pushup(int root){
 7     for(int i=0;i<3;i++){
 8         sum[root][i]=sum[root*2][i]+sum[root*2+1][i];
 9     }
10 }
11 void pushdown(int root){
12     int lr=root*2,rr=root*2+1,tem;
13     if(lazy[root] != 0) {
14         lazy[lr] =(lazy[lr]+lazy[root])%3;
15         lazy[rr]=(lazy[rr]+lazy[root])%3;
16         if(lazy[root]==1){
17             tem=sum[lr][1];
18             sum[lr][1]=sum[lr][0];
19             sum[lr][0]=sum[lr][2];
20             sum[lr][2]=tem;
21         }
22         else if(lazy[root]==2){
23             tem=sum[lr][1];
24             sum[lr][1]=sum[lr][2];
25             sum[lr][2]=sum[lr][0];
26             sum[lr][0]=tem;
27         }
28         if(lazy[root]==1){
29             tem=sum[rr][1];
30             sum[rr][1]=sum[rr][0];
31             sum[rr][0]=sum[rr][2];
32             sum[rr][2]=tem;
33         }
34         else if(lazy[root]==2){
35             tem=sum[rr][1];
36             sum[rr][1]=sum[rr][2];
37             sum[rr][2]=sum[rr][0];
38             sum[rr][0]=tem;
39         }
40         lazy[root]=0;
41     }
42 }
43 void build(int l,int r,int root){
44     lazy[root]=0,sum[root][0]=1,sum[root][1]=0,sum[root][2]=0;
45     if(l==r)return ;
46     int mid=(l+r)/2;
47     build(l,mid,root*2);
48     build(mid+1,r,root*2+1);
49     pushup(root);
50 }
51 void update(int x,int y,int l,int r,int root){
52     int mid=(r+l)/2,tem;
53     if(x<=l&&y>=r){
54         lazy[root]=(1+lazy[root])%3;
55         tem=sum[root][1];
56         sum[root][1]=sum[root][0];
57         sum[root][0]=sum[root][2];
58         sum[root][2]=tem;
59         return ;
60     }
61     pushdown(root);
62     if(x<=mid)update(x,y,l,mid,root*2);
63     if(y>mid)update(x,y,mid+1,r,root*2+1);
64     pushup(root);
65 }
66 int query(int x,int y,int l,int r,int root){
67     if(x<=l&&y>=r){
68         return sum[root][0];
69     }
70     pushdown(root);
71     int mid=(r+l)/2,ans=0;
72     if(x<=mid)ans+=query(x,y,l,mid,root*2);
73     if(y>mid)ans+=query(x,y,mid+1,r,root*2+1);
74     return ans;
75 }
76 int main(){
77     //freopen("test.txt","r",stdin);
78     int n,q,x,y,z;
79         scanf("%d%d",&n,&q);
80         build(0,n,1);
81         for(int i=0;i<q;i++){
82             scanf("%d%d%d",&z,&x,&y);
83             if(z==1)printf("%d\n",query(x,y,0,n,1));
84             else update(x,y,0,n,1);
85         }
86     return 0;
87 }