题目描述 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
思路：每个点记录%%%%7=0,1,2,3,4,5,6,的个数
代码：
#include<bits/stdc++.h> using namespace std; #define maxn 1000000 int n,m,a[7]; string s; char Cget; void read(int &now) { Cget=getchar(); now=0; while(Cget>'9'||Cget<'0') { Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } } struct TreeType{ int l,r,flag,w,sum[7]; }tree[maxn<<2]; void tree_up(int k) { tree[k].w=tree[k<<1].w+tree[k<<1|1].w; for(int i=0;i<=6;i++) tree[k].sum[i]=tree[k<<1].sum[i]+tree[k<<1|1].sum[i]; } void tree_down(int k) { tree[k<<1].flag+=tree[k].flag; tree[k<<1|1].flag+=tree[k].flag; int x=tree[k].flag; for(int i=0;i<=6;i++) a[i]=tree[k<<1].sum[i]; for(int i=0;i<=6;i++) tree[k<<1].sum[(i+x)%7]=a[i]; for(int i=0;i<=6;i++) a[i]=tree[k<<1|1].sum[i]; for(int i=0;i<=6;i++) tree[k<<1|1].sum[(i+x)%7]=a[i]; tree[k].flag=0; } void tree_build(int l,int r,int k) { tree[k].l=l; tree[k].r=r; if(l==r) { read(tree[k].w); tree[k].sum[tree[k].w%7]++; return ; } int mid=(l+r)>>1; tree_build(l,mid,k<<1); tree_build(mid+1,r,k<<1|1); tree_up(k); } void tree_change(int l,int r,int k,int x) { if(tree[k].l==l&&tree[k].r==r) { tree[k].flag+=x; int a[7]; for(int i=0;i<=6;i++) a[i]=tree[k].sum[i]; for(int i=0;i<=6;i++) tree[k].sum[(i+x)%7]=a[i]; return ; } if(tree[k].flag) tree_down(k); int mid=(tree[k].l+tree[k].r)>>1; if(l>mid) tree_change(l,r,k<<1|1,x); else if(r<=mid) tree_change(l,r,k<<1,x); else{ tree_change(l,mid,k<<1,x); tree_change(mid+1,r,k<<1|1,x); } tree_up(k); } int tree_query(int l,int r,int k) { if(tree[k].l==l&&tree[k].r==r) return tree[k].sum[0]; int mid=(tree[k].l+tree[k].r)>>1; if(tree[k].flag) tree_down(k); if(l>mid) return tree_query(l,r,k<<1|1); else if(r<=mid) return tree_query(l,r,k<<1); else return tree_query(l,mid,k<<1)+tree_query(mid+1,r,k<<1|1); } int main() { read(n); tree_build(1,n,1); read(m); int x,y,z; for(int i=1;i<=m;i++) { cin>>s; if(s[0]=='a') { cin>>x>>y>>z; tree_change(x,y,1,z); } else{ cin>>x>>y; int ans=tree_query(x,y,1); cout<<ans<<endl; } } }