class="markdown_views prism-atom-one-light">

题意分析

emmmm WA了一天
我一直以为是区间修改写挂了，然后发现其实策略PUSHUP，PUSHDOWN写的不好。 首先考虑，在建树的时候，叶子节点不必保存数值。
其次，在更新的时候，只需要更新更新数值模7的结果。 如果模7为0，则不必更新。
在更新的时候，只需要对保存模7余几的那个数组进行相应修改，别的不用管了。 PUSHUP：将节点左右儿子的结果进行合并。
PUSHDOWN：对于叶子节点不必PUSHDOWN，对于lazy = 0的节点也不必PUSHDOWN。在PUSHDOWN的时候标记下传，同时对左右儿子的结果进行更新。

代码总览

#include #include #include #define nmax 100010 using namespace std; struct Tree{ int l,r; int lazy; int tans[7]; int mid(){ return (l+r)>>1; } }; Tree tree[nmax<<2]; int num[nmax]; int N,Q,a,b; int c; char op[40]; void change(int rt ,int val){ int temp[7] = {0}; for(int i = 0;i<7;++i) temp[ (i+ val) % 7] = tree[rt].tans[i]; for(int i = 0;i<7;++i) tree[rt].tans[i] = temp[i]; } void PushUp(int rt){ for(int i = 0;i<7;++i) tree[rt].tans[i] = tree[rt<<1].tans[i] + tree[rt<<1|1].tans[i]; } void PushDown(int rt){ if(!tree[rt].lazy || tree[rt].l == tree[rt].r) return; tree[rt<<1].lazy += tree[rt].lazy; tree[rt<<1|1].lazy += tree[rt].lazy; change(rt<<1,tree[rt].lazy); change(rt<<1|1,tree[rt].lazy); tree[rt].lazy = 0; } void Build(int l, int r, int rt){ tree[rt].l = l; tree[rt].r = r; tree[rt].lazy = 0; if(l == r){ tree[rt].tans[num[l] % 7] = 1; return; } Build(l,tree[rt].mid(),rt<<1); Build(tree[rt].mid()+1,r,rt<<1|1); PushUp(rt); } void UpdateInterval(int val, int l, int r, int rt) { if(tree[rt].l >= l && tree[rt].r <= r){ tree[rt].lazy += val; change(rt,val); return; } PushDown(rt); if(l <= tree[rt].mid()) UpdateInterval(val,l,r,rt<<1); if(r > tree[rt].mid()) UpdateInterval(val,l,r,rt<<1|1); PushUp(rt); } int Query(int l,int r,int rt){ PushDown(rt); if(l <= tree[rt].l && tree[rt].r <= r ) return tree[rt].tans[0]; int ans = 0; if(l<= tree[rt].mid()) ans += Query(l,r,rt<<1); if(r> tree[rt].mid()) ans += Query(l,r,rt<<1|1); return ans; } int main(){ scanf("%d",&N); for(int i = 1;i<=N;++i) scanf("%d",&num[i]); Build(1,N,1); scanf("%d",&Q); for(int i = 0;iscanf(" %s %d %d",op,&a,&b); if(!strcmp(op,"add")){ scanf("%d",&c); c = c % 7; if(c) UpdateInterval(c,a,b,1); }else{ printf("%d ",Query(a,b,1)); } } return 0; }