题目描述 Description
给你N个数，有两种操作
1：给区间[a,b]内的所有数都增加X
2：询问区间[a,b]能被7整除的个数
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是add，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是count，表示统计区间[a,b]能被7整除的个数
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3 2 3 4 6 count 1 3 count 1 2 add 1 3 2 count 1 3 add 1 3 3 count 1 3
样例输出 Sample Output
0
0
0
1
数据范围及提示 Data Size & Hint
10%:1<N<=10,1<Q<=10
30%:1<N<=10000,1<Q<=10000
100%:1<N<=100000,1<Q<=100000
思路：
对当前dis取模7；
然后根据余数来建立个数；
然后每次增加都交换即可；
来，上代码：
#include <cstdio> #include <iostream> using namespace std; struct TreeNodeType { int l,r,mid,flag,dis[7]; }; struct TreeNodeType tree[100005<<2]; int if_z,n,m; char Cget; inline void in(int &now) { now=0,if_z=1,Cget=getchar(); while(Cget>'9'||Cget<'0') { if(Cget=='-') if_z=-1; Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } now*=if_z; } inline void tree_up(int now) { for(int i=0;i<=6;i++) { tree[now].dis[i]=tree[now<<1].dis[i]+tree[now<<1|1].dis[i]; } } void tree_build(int now,int l,int r) { tree[now].l=l,tree[now].r=r; if(l==r) { int pos; in(pos); tree[now].dis[pos%7]++; return ; } tree[now].mid=(l+r)>>1; tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); tree_up(now); } inline void tree_down(int now) { int pos=tree[now].flag,tmp[7]; tree[now<<1].flag+=pos; tree[now<<1|1].flag+=pos; for(int i=0;i<=6;i++) tmp[i]=tree[now<<1].dis[i]; for(int i=0;i<=6;i++) { tree[now<<1].dis[(i+pos)%7]=tmp[i]; tmp[i]=tree[now<<1|1].dis[i]; } for(int i=0;i<=6;i++) tree[now<<1|1].dis[(i+pos)%7]=tmp[i]; tree[now].flag=0; } void tree_change(int now,int l,int r,int x) { if(tree[now].l==l&&tree[now].r==r) { int tmp[7]; for(int i=0;i<=6;i++) tmp[i]=tree[now].dis[i]; for(int i=0;i<=6;i++) tree[now].dis[(i+x)%7]=tmp[i]; tree[now].flag+=x; return ; } if(tree[now].flag) tree_down(now); if(l>tree[now].mid) tree_change(now<<1|1,l,r,x); else if(r<=tree[now].mid) tree_change(now<<1,l,r,x); else { tree_change(now<<1,l,tree[now].mid,x); tree_change(now<<1|1,tree[now].mid+1,r,x); } tree_up(now); } int tree_query(int now,int l,int r) { if(tree[now].l==l&&tree[now].r==r) return tree[now].dis[0]; if(tree[now].flag) tree_down(now); if(l>tree[now].mid) return tree_query(now<<1|1,l,r); else if(r<=tree[now].mid) return tree_query(now<<1,l,r); else return tree_query(now<<1,l,tree[now].mid)+tree_query(now<<1|1,tree[now].mid+1,r); } int main() { in(n); tree_build(1,1,n); in(m);char ch[10]; int l,r,x; while(m--) { cin>>ch; if(ch[0]=='a') { in(l),in(r),in(x); tree_change(1,l,r,x); } else { in(l),in(r); printf("%d ",tree_query(1,l,r)); } } return 0; }