题解引自:http://www.cnblogs.com/wuyiqi/archive/2012/05/27/2520642.html
题意:
有n个数，刚开始都为0
add i , j 给i,j区间内的数都加1
Q i j 询问i、j间能被三整除的数的个数
分析:
线段树记录三个域
对三取余为0的数的个数
。。。。。1.。。。。。
。。。。。2.。。。。。
可以保存在一个数组里面
考虑到每次给一个区间加1的时候，区间内对3取余为1的数的个数变成了对三取余为2,2的变成了0,0的变成了1
所以每次更新到区间或者把信息（懒惰标记）往下传的时候只需要把相应的域做一下调整即可
// File Name: 1135.cpp // Author: Zlbing // Created Time: 2013/7/18 21:47:54 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int MAXN=1e5+100; int col[MAXN<<2]; int sum[MAXN<<2][3]; int n,q; void pushup(int rt) { for(int i=0;i<3;i++) sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][i]; } void build(int l,int r,int rt) { col[rt]=0; if(l==r) { sum[rt][0]=1; sum[rt][1]=sum[rt][2]=0; return; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } void make(int rt) { swap(sum[rt][2],sum[rt][0]); swap(sum[rt][1],sum[rt][2]); } void pushdown(int rt) { if(col[rt]) { col[rt<<1]+=col[rt]; col[rt<<1|1]+=col[rt]; for(int i=0;i<col[rt]%3;i++) { make(rt<<1); make(rt<<1|1); } } col[rt]=0; } void update(int L,int R,int l,int r,int rt) { if(L<=l&&R>=r) { col[rt]++; make(rt); return; } pushdown(rt); int m=(l+r)>>1; if(L<=m)update(L,R,lson); if(R>m)update(L,R,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&R>=r) { return sum[rt][0]; } pushdown(rt); int m=(l+r)>>1; int ret=0; if(L<=m)ret+=query(L,R,lson); if(R>m)ret+=query(L,R,rson); return ret; } int main() { int T; int cas=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); int a,b,c; build(1,n,1); printf("Case %d: ",cas++); for(int i=0;i<q;i++) { scanf("%d%d%d",&a,&b,&c); b++,c++; if(a==0)update(b,c,1,n,1); if(a==1){ printf("%d ",query(b,c,1,n,1)); } } } return 0; }