4919 线段树练习4
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
查看运行结果
题目描述 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 46count 1 3count 1 2add 1 3 2count 1 3add 1 3 3count 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#include 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\n",tree_query(1,l,r)); } } return 0;}