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

2022-06-16 02:04:05

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=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 80010

#define P 19940417

int N,Q,C[MAXN][];

namespace SegmentTree

{

    struct SumNode{int sum[];};

    struct SegmentTreeNode{int l,r,size,tag; SumNode p; bool rev;}tree[MAXN<<];

    #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<) x+=P;}

    inline SumNode Merge(SegmentTreeNode x,SegmentTreeNode y)

    {

        SumNode re; re.sum[]=;

        for (int i=; i<=; i++)

            {

                re.sum[i]=(x.p.sum[i]+y.p.sum[i])%P;

                for (int j=; j<=i-; 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^=;

        if (tree[now].tag) tree[now].tag=(P-tree[now].tag%P)%P;

        for (int i=; i<=; i++) if ((i&) && 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=; i; i--,t=D)

            {

                for (int j=i-; 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=;}

        if (tree[now].tag) {change(ls,tree[now].tag); change(rs,tree[now].tag); tree[now].tag=;}

    }

    inline void BuildTree(int now,int l,int r)

    {

        tree[now].l=l; tree[now].r=r; tree[now].size=r-l+;

        tree[now].p.sum[]=; tree[now].tag=; tree[now].rev=;

        if (l==r) {tree[now].p.sum[]=(read()+P)%P; return;}

        int mid=(l+r)>>;

        BuildTree(ls,l,mid); BuildTree(rs,mid+,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)>>;

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

        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)>>; 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+,R,D)),re;

    }

}

void GetC()

{

    C[][]=;

    for (int i=; i<=N; i++)

        {

            C[i][]=;

            for (int j=; j<=min(i,); j++) C[i][j]=(C[i-][j]+C[i-][j-])%P;

        }

}

using namespace SegmentTree;

int main()

{

//  freopen("sequence.in","r",stdin);

//  freopen("sequence.out","w",stdout);

    N=read(),Q=read();

    GetC();

    SegmentTree::BuildTree(,,N);

//  for (int i=1; i<=N; i++) printf("%I64d  ",Query(1,1,N,i).p.sum[i]); puts("");

//  puts("============================================");

    while (Q--)

        {

            char opt[]; scanf("%s",opt); int x,y,z;

            switch (opt[])

                {

                    case 'I' : x=read(),y=read(),z=(read()+P)%P; SegmentTree::Change(,x,y,z); break;

                    case 'Q' : x=read(),y=read(),z=read(); printf("%d\n",SegmentTree::Query(,x,y,z).p.sum[z]); break;

                    case 'R' : x=read(),y=read(); SegmentTree::Reverse(,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，BZOJ楞是WA，就是不报RE，小数据妥妥拍不到，纸张

差点搞得自己以后再也不能叫char哥....

码农公寓