【BZOJ-2962】序列操作线段树 + 区间卷积

2962: 序列操作

Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 678 Solved: 246
[Submit][Status][Discuss]

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

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。

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)。

Source

中国国家队清华集训 2012-2013 第三天

Solution

线段树维护区间卷积

我们每个区间维护sum[1~20]分别表示选1~20个数的积的和

然后问题在于合并以及修改

合并非常简单$rt.sum[i]=\sum_{j=1}^{i}ls.sum[j]*rs.sum[i-j]$ （手写小的就可以得到）

至于区间取反，直接对区间的所有奇数$sum$取反，偶数$sum$不变。因为偶数里的全是偶数项，负号会抵消

区间修改，问题是下放标记时，我们发现假设我们有三个数a，b，c；我们修改时同时+x，那么他们的变化就是

$(a+x)*(b+x)*(c+x)=abc+x(ab+ac+bc)+x^{2}(a+b+c)+x^{3}$这样我们发现，拓展到之后可以得到$sum[i]=\sum_{j=0}^{i}sum[i-j]*C_{sz-j}^{i}*x^{i-j}$

然后我们就可以利用线段树维护了，特别地$sum[0]=1$，中间过程会爆int;

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define MAXN 80010
#define P 19940417
int N,Q,C[MAXN][21];
namespace SegmentTree
{
    struct SumNode{int sum[25];};
    struct SegmentTreeNode{int l,r,size,tag; SumNode p; bool rev;}tree[MAXN<<2];
    #define ls now<<1
    #define rs now<<1|1
    inline void Add(int &x,int y) {x+=y; while (x>=P) x-=P; while (x<0) x+=P;}
    inline SumNode Merge(SegmentTreeNode x,SegmentTreeNode y)
    {
        SumNode re; re.sum[0]=1;
        for (int i=1; i<=20; i++)
            {
                re.sum[i]=(x.p.sum[i]+y.p.sum[i])%P;
                for (int j=1; j<=i-1; j++)
                    Add(re.sum[i],(LL)x.p.sum[j]*y.p.sum[i-j]%P);
            }
        return re;
    }   
    inline void Update(int now) {tree[now].p=Merge(tree[ls],tree[rs]);}
    inline void rever(int now)
    {
        tree[now].rev^=1;
        if (tree[now].tag) tree[now].tag=(P-tree[now].tag%P)%P;
        for (int i=1; i<=20; i++) if ((i&1) && tree[now].p.sum[i]) tree[now].p.sum[i]=(P-tree[now].p.sum[i])%P;
    }
    inline void change(int now,int D)
    {
        Add(tree[now].tag,D);
        for (int t=D,i=20; i; i--,t=D)
            {
                for (int j=i-1; j; j--,t=(LL)t*D%P) 
                    Add(tree[now].p.sum[i],(LL)t*tree[now].p.sum[j]%P*C[tree[now].size-j][i-j]%P);
                Add(tree[now].p.sum[i],(LL)t*C[tree[now].size][i]%P);
            }
    }
    inline void PushDown(int now)
    {
        if (tree[now].rev) {rever(ls); rever(rs); tree[now].rev=0;}
        if (tree[now].tag) {change(ls,tree[now].tag); change(rs,tree[now].tag); tree[now].tag=0;}
    }
    inline void BuildTree(int now,int l,int r)
    {
        tree[now].l=l; tree[now].r=r; tree[now].size=r-l+1; 
        tree[now].p.sum[0]=1; tree[now].tag=0; tree[now].rev=0;
        if (l==r) {tree[now].p.sum[1]=(read()+P)%P; return;}
        int mid=(l+r)>>1;
        BuildTree(ls,l,mid); BuildTree(rs,mid+1,r);
        Update(now);
    }
    inline void Reverse(int now,int L,int R)
    {
        int l=tree[now].l,r=tree[now].r;
        if (L<=l && R>=r) {rever(now); return;}
        PushDown(now);
        int mid=(l+r)>>1;
        if (L<=mid) Reverse(ls,L,R);
        if (R>mid) Reverse(rs,L,R);
        Update(now);
    }
    inline void Change(int now,int L,int R,int D)
    {
        int l=tree[now].l,r=tree[now].r;
        if (L<=l && R>=r) {change(now,D); return;}
        PushDown(now);
        int mid=(l+r)>>1;
        if (L<=mid) Change(ls,L,R,D);
        if (R>mid) Change(rs,L,R,D);
        Update(now);
    }
    inline SegmentTreeNode Query(int now,int L,int R,int D)
    {
        int l=tree[now].l,r=tree[now].r;
        if (L==l && R==r) return tree[now];
        PushDown(now);
        int mid=(l+r)>>1; SegmentTreeNode re;
        if (R<=mid) return Query(ls,L,R,D);
            else if (L>mid) return Query(rs,L,R,D);
                else return re.p=Merge(Query(ls,L,mid,D),Query(rs,mid+1,R,D)),re;
    }
}
void GetC()
{
    C[0][0]=1;
    for (int i=1; i<=N; i++)
        {
            C[i][0]=1;
            for (int j=1; j<=min(i,20); j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
        }
}
using namespace SegmentTree;
int main()
{
//  freopen("sequence.in","r",stdin);
//  freopen("sequence.out","w",stdout);
    N=read(),Q=read();
    GetC();
    SegmentTree::BuildTree(1,1,N);
//  for (int i=1; i<=N; i++) printf("%I64d  ",Query(1,1,N,i).p.sum[i]); puts("");
//  puts("============================================"); 
    while (Q--)
        {
            char opt[2]; scanf("%s",opt); int x,y,z;
            switch (opt[0])
                {
                    case 'I' : x=read(),y=read(),z=(read()+P)%P; SegmentTree::Change(1,x,y,z); break;
                    case 'Q' : x=read(),y=read(),z=read(); printf("%d\n",SegmentTree::Query(1,x,y,z).p.sum[z]); break;
                    case 'R' : x=read(),y=read(); SegmentTree::Reverse(1,x,y); break;
                }
//          puts("============================================");      
//          for (int i=1; i<=N; i++) printf("%d\n",Query(1,1,N,i).p.sum[i]); puts("");
//          printf("%d %d %d\n",x,y,z);
//          puts("============================================"); 
        }
    return 0;
}