【BZOJ2962】序列操作
Description
有一个长度为n的序列，有三个操作1.I a b c表示将[a,b]这一段区间的元素集体增加c，2.R a b表示将[a,b]区间内所有元素变成相反数，3.Q a b c表示询问[a,b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。
Input
第一行两个数n，q表示序列长度和操作个数。
第二行n个非负整数，表示序列。
接下来q行每行输入一个操作I a b c或者 R a b或者Q a b c意义如题目描述。
Output
对于每个询问，输出选出c个数相乘的所有方案的和mod19940417的值。
Sample Input
5 5
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1
Sample Output
40
19940397
样例说明
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为3*4+3*4+4*4=40。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为-2-4-5-4-5=-20。
19940397
样例说明
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为3*4+3*4+4*4=40。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为-2-4-5-4-5=-20。
HINT
100%的数据n<=50000,q<=50000,初始序列的元素的绝对值<=109，I a b c中保证[a,b]是一个合法区间，|c|<=109，R a b保证[a,b]是个合法的区间。Q a b c中保证[a,b]是个合法的区间1<=c<=min(b-a+1,20)。
题解：线段树套路题。对于线段树上的每个节点都维护s[i]表示当前区间取出i个数的所有方案的和，然后区间合并的时候就是求卷积，区间取反的时候就是将奇数位取反，区间加的时候比较麻烦，用组合数搞一搞就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const ll P=19940417;
const int maxn=50010;
int n,m;
ll C[maxn][22];
int v[maxn];
char str[5];
struct node
{
ll ts;
int tf,siz;
ll a[21];
ll & operator [] (int b) {return a[b];}
node () {memset(a,0,sizeof(a)),ts=tf=siz=0;}
node operator + (node b)
{
node c;
register int i,j;
for(i=0;i<=20;i++) for(j=0;i+j<=20;j++) c[i+j]=(c[i+j]+a[i]*b[j])%P;
c.siz=siz+b.siz;
return c;
}
inline void rev()
{
for(register int i=1;i<20;i+=2) a[i]=(P-a[i])%P;
ts=(P-ts)%P,tf^=1;
}
inline void add(ll x)
{
ts=(ts+x)%P;
register int i,j;
register ll y;
for(i=min(20,siz);i;i--)
{
for(y=x,j=1;j<i;y=y*x%P,j++) a[i]=(a[i]+y*a[i-j]%P*C[siz-i+j][j])%P;
a[i]=(a[i]+C[siz][i]*y)%P;
}
}
}s[maxn<<2];
inline void pushdown(int x)
{
if(s[x].tf) s[lson].rev(),s[rson].rev(),s[x].tf=0;
if(s[x].ts) s[lson].add(s[x].ts),s[rson].add(s[x].ts),s[x].ts=0;
}
void build(int l,int r,int x)
{
if(l==r)
{
s[x].siz=s[x][0]=1,s[x][1]=v[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
s[x]=s[lson]+s[rson];
}
void up1(int l,int r,int x,int a,int b,ll c)
{
if(a<=l&&r<=b)
{
s[x].add(c);
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(a<=mid) up1(l,mid,lson,a,b,c);
if(b>mid) up1(mid+1,r,rson,a,b,c);
s[x]=s[lson]+s[rson];
}
void up2(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b)
{
s[x].rev();
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(a<=mid) up2(l,mid,lson,a,b);
if(b>mid) up2(mid+1,r,rson,a,b);
s[x]=s[lson]+s[rson];
}
node query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s[x];
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) return query(l,mid,lson,a,b);
if(a>mid) return query(mid+1,r,rson,a,b);
return query(l,mid,lson,a,b)+query(mid+1,r,rson,a,b);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i,j,a,b,c;
for(i=0;i<=n;i++)
{
C[i][0]=1;
for(j=1;j<=min(i,20);j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
}
for(i=1;i<=n;i++) v[i]=rd()%P;
build(1,n,1);
for(i=1;i<=m;i++)
{
scanf("%s",str),a=rd(),b=rd();
if(str[0]=='I') c=rd(),up1(1,n,1,a,b,(c+P)%P);
if(str[0]=='R') up2(1,n,1,a,b);
if(str[0]=='Q') c=rd(),printf("%lld\n",(query(1,n,1,a,b).a[c]+P)%P);
}
return 0;
}//5 5 1 2 3 4 5 I 2 3 1 Q 2 4 2 R 1 5 I 1 3 -1 Q 1 5 1