4919 线段树练习4
时间限制: 1 s
空间限制: 128000 KB
题目描述 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
这道题的比较裸，需要思考的只有如何pushup和change信息。
对于线段树里存的元素是一个桶，记录这一段余数为1,2,3,4,5,6,0的分别有多少。
在pushup时只需将ls和rs的桶相加即可（代码11行）
在修改时则只需将数组内的是s[i]元素想右移动s[(i+a)%7]即可.
其他基本与普通线段树无异。
#include<cstdio>
#include<cstring>
#define ls x<<1
#define rs x<<1|1
const int N=;
int lazy[N<<];
struct X
{
int s[];
X() {memset(s,,sizeof(s));};
void pu(const X &a,const X &b)
{
for(int i=;i<;i++)
s[i]=a.s[i]+b.s[i];
}
void gb(int x)
{
X t;
for(int i=;i<;i++) t.s[(i+x)%]=s[i];
*this=t;
}
}tree[N<<];
char c[];
void pd(int x)
{
if(lazy[x])
{
lazy[ls]+=lazy[x];
lazy[rs]+=lazy[x];
tree[ls].gb(lazy[x]);
tree[rs].gb(lazy[x]);
lazy[x]=;
}
}
void bu(int l,int r,int x)
{
if(l==r)
{
int a;
scanf("%d",&a);
tree[x].s[a%]=;
}
else
{
int mid=(l+r)>>;
bu(l,mid,ls);
bu(mid+,r,rs);
tree[x].pu(tree[ls],tree[rs]);
}
}
void chan(int l,int r,int x,int s,int ql,int qr)
{
if(ql<=l&&qr>=r) lazy[x]+=s,tree[x].gb(s);
else
{
int mid=(l+r)>>;
pd(x);
if(mid>=ql) chan(l,mid,ls,s,ql,qr);
if(qr>mid) chan(mid+,r,rs,s,ql,qr);
tree[x].pu(tree[ls],tree[rs]);
}
}
int ask(int l,int r,int x,int ql,int qr)
{
if(ql<=l&&qr>=r) return tree[x].s[];
else
{
int mid=(l+r)>>,re=;
pd(x);
if(mid>=ql) re+=ask(l,mid,ls,ql,qr);
if(qr>mid) re+=ask(mid+,r,rs,ql,qr);
tree[x].pu(tree[ls],tree[rs]);
return re;
}
}
int main()
{
int n,q;
scanf("%d",&n);
bu(,n,);
scanf("%d",&q);
while(q--)
{
scanf("%s",c);
if(c[]=='a')
{
int tj,l,r;
scanf("%d%d%d",&l,&r,&tj);
chan(,n,,tj,l,r);
}
else
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",ask(,n,,l,r));
}
}
return ;
}