题目描述

有一个长度为\(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\)的值。

对于100%的数据，\(n \leq 50000, q \leq 50000\)，初始序列的元素的绝对值\(\leq 10^9\)，保证\([a,b]\)是一个合法区间，I操作中\(|c| \leq 10^9\)，Q操作中\(1 \leq c \leq \min(b-a+1,20)\)。

思路

\(1.\) 区间加，线段树基础操作。

\(2.\) 取反，显而易见奇变偶不变。

\(3.\) 查询，发现 \(c\) 的值域很小，我们可直接维护答案。

细节

\(1.\)上传 \(pushup\)

考虑 DP

\(f_{l,r,c}=f_{l,mid,i}* f_{mid+1,r,j}(i+j=c)\)

\(2.\)区间加时更新答案

手写几项展开可发现

\(f_{l,r,c}= \sum\limits_{i=0}^{c}f_{l,r,i} \cdot x^{c-i}\cdot C_{r-l+1-i}^{c-i}\)

可先预处理出杨辉三角形

\(3.\)标记优先级

取反时，要将加标记取反。

取反先于加法

固定模数一定要加const！！！！！

2 h就废在这上面了（算是首黑纪念了）

Code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p,k) tree[p].sum[k]
#define chg(p) tree[p].chg
#define add(p) tree[p].add
const int N = 60005,M=20005,mod=19940417;

int n,q,y,l,r,pos;                  `
LL c[N][25],d[50],x;
char op[2];
struct Segment_tree{
    int l,r,chg;
    LL sum[25],add;
}tree[N*4];

inline int min(int a,int b){
    return a<b?a:b
}
inline LL readc(){
    char ch=getchar();
    while(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))) ch=getchar();
    return ch;
}
inline LL read(){
    LL s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
    return s*w;
}
inline void print(LL x){
    char F[200];LL cnt=0;
    if(x==0){putchar('0');putchar('\n');return ;}
    if(x<0){putchar('-');x=-x;}
    while(x){F[++cnt]=x%10;x/=10;}
    while(cnt) putchar(F[cnt--]+'0');
    putchar('\n');return ;
}

void ad(int p,int k){
    if(!k||!p) return ;
    int l1=min(20,r(p)-l(p)+1);
    d[0]=1;
    for(int i=1;i<=l1;i++) d[i]=(d[i-1]*k)%mod;
    for(int i=l1;i>=1;i--){
        for(int j=0;j<i;j++){
            sum(p,i)=(sum(p,i)+((sum(p,j)*d[i-j]%mod)*c[r(p)-l(p)+1-j][i-j])%mod)%mod;
        }
    }
    add(p)=(add(p)+k)%mod;
    return ;
}

void ch(int p){
    if(!p) return ;
    for(int i=1;i<=min(20,r(p)-l(p)+1);i+=2)
    sum(p,i)=(mod-sum(p,i))%mod;
    add(p)=(mod-add(p))%mod;
    chg(p)^=1;
    return ;
}

void pushup(int p){
    int l1=min(20,r(p)-l(p)+1),l2=min(20,r(p<<1)-l(p<<1)+1),l3=min(20,r(p<<1|1)-l(p<<1|1)+1);
    for(int i=0;i<=l1;i++) sum(p,i)=0;
    for(int i=0;i<=l2;i++)
    for(int j=0;j<=l3;j++){
        if(i+j>20) break;
        sum(p,i+j)=(sum(p,i+j)+sum(p<<1,i)*sum(p<<1|1,j)%mod)%mod;
    }
    return ;
}

void pushdown(int p){
    if(chg(p)){
        ch(p<<1);ch(p<<1|1);
        chg(p)=0;
    }
    if(add(p)){
        ad(p<<1,add(p));
        ad(p<<1|1,add(p));
        add(p)=0;
    }
    return ;
}

void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    sum(p,0)=1;
    if(l==r){
        sum(p,1)=(read()%mod+mod)%mod;
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
    return ;
}

void change(int p,int l,int r,LL x,LL op){
    if(l(p)>=l&&r(p)<=r){
        if(op==1)
            ad(p,x);
        else
            ch(p);
        return ;
    }
    pushdown(p);
    int mid=(l(p)+r(p))>>1;
    if(l<=mid) change(p<<1,l,r,x,op);
    if(r>mid) change(p<<1|1,l,r,x,op);
    pushup(p);
    return ;
}

Segment_tree merge(Segment_tree ls,Segment_tree rs,int x){
    x=20;
    Segment_tree now;
    now.r=rs.r,now.l=ls.l;
    int l1=min(x,now.r-now.l+1),l2=min(x,ls.r-ls.l+1),l3=min(x,rs.r-rs.l+1);
    for(int i=0;i<=l1;i++) now.sum[i]=0;
    for(int i=0;i<=l2;i++)
    for(int j=0;j<=l3;j++){
        if(i+j>x) break;
        now.sum[i+j]=(now.sum[i+j]+ls.sum[i]*rs.sum[j]%mod)%mod;
    }
    return now;
}

Segment_tree query(int p,int l,int r,int x){
    if(l(p)>=l&&r(p)<=r) return tree[p];
    pushdown(p);
    LL mid=(l(p)+r(p))>>1;
    if(r<=mid) return query(p<<1,l,r,x);
    else
    if(l>mid) return query(p<<1|1,l,r,x);
    else return merge(query(p<<1,l,r,x),query(p<<1|1,l,r,x),x);
}

int main(){
    n=read(),q=read();
    c[0][0]=1;c[1][0]=1;c[1][1]=1;
    for(int i=2;i<=N-5;i++){
        c[i][0]=1;
        for(int j=1;j<=min(20,i);j++){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        cin>>op;l=read(),r=read();
        if(op[0]=='I'){
            x=read();
            x%=mod;
            change(1,l,r,(x+mod)%mod,1);
        }else
        if(op[0]=='R'){
            change(1,l,r,0,0);
        }else
        if(op[0]=='Q'){
            x=read();
            print((query(1,l,r,x).sum[x]+mod)%mod);
        }
    }
    return 0;
}

发布时间：2022-11-16 18:45