M_sea

洛谷4247 [清华集训]序列操作
LuoguBZOJ分析线段树。首先考虑需要哪些标记。容易知道我们打一个区间加和区间取反的标记就行了。然后每个节点维...
扫描右侧二维码阅读全文
07
2019/03

洛谷4247 [清华集训]序列操作

Luogu

BZOJ

分析

线段树。

首先考虑需要哪些标记。容易知道我们打一个区间加和区间取反的标记就行了。

然后每个节点维护一个 $c[i]$ 表示这段区间任选 $i$ 个数的答案。


下面考虑 $3$ 种操作。

区间加

首先,区间加的标记累加当前加的值。

重点考虑怎么修改 $c$ 数组。

假如我们选前 $15$ 个数乘起来,也就是 $(a_1,a_2,...,a_{15})$ 变成了 $(a_1+v,a_2+v,...,a_{15}+v)$ 。

那么 $c_{15}$ 变成了 $C_{len-15}^0 \cdot v^0 \cdot c_{15} + C_{len-14}^1 \cdot v^1 \cdot c_{14} + C_{len-13}^2 \cdot v^2 \cdot c_{13} + \cdots + C_{len-0}^{15} \cdot v^{15} \cdot c_0$ 。

于是可以预处理杨辉三角,然后倒序修改。

区间取反

首先把区间取反的标记异或 $1$ 。

因为奇数个 $-1$ 的积为 $-1$ ,偶数个 $-1$ 的积为 $1$ ,所以只要将奇数项取反即可。

同理,还要将区间加的标记取反。

区间查询

考虑怎么把左右两个区间合并。

可以得到 $c_i=\sum\limits_{j=0}^i cl_j\times cr_{i-j}$ 。


具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int N=50000+10;
const int mod=19940417;

int a[N];
int C[N][21],tmp[21];

struct segment_tree {
    struct node {
        ll c[21],addv; int revv,len;
        node() { addv=revv=len=0; memset(c,0,sizeof(c)); }
    } t[N<<2];
    
#define ls (o<<1)
#define rs (o<<1|1)

    inline void add(int o,int v) {
        tmp[0]=1;
        for (re int i=1;i<=20&&i<=t[o].len;++i) tmp[i]=1ll*tmp[i-1]*v%mod;
        for (re int i=min(20,t[o].len);i>=1;--i)
            for (re int j=0;j<i;++j)
                t[o].c[i]=(t[o].c[i]+t[o].c[j]*tmp[i-j]%mod*C[t[o].len-j][i-j]%mod)%mod;
        t[o].addv=(t[o].addv+v)%mod;
    }
    inline void rev(int o) {
        for (re int i=1;i<=20&&i<=t[o].len;++i)
            if (i&1) t[o].c[i]=mod-t[o].c[i];
        t[o].addv=mod-t[o].addv,t[o].revv^=1;
    }
    inline node merge(node a,node b) {
        node res; res.len=a.len+b.len;
        for (re int i=0;i<=20&&i<=a.len;++i)
            for (re int j=0;i+j<=20&&j<=b.len;++j)
                res.c[i+j]=(res.c[i+j]+a.c[i]*b.c[j]%mod)%mod;
        return res;
    }
    
    inline void pushup(int o) {
        memset(t[o].c,0,sizeof(t[o].c));
        for (re int i=0;i<=20&&i<=t[ls].len;++i)
            for (re int j=0;i+j<=20&&j<=t[rs].len;++j)
                t[o].c[i+j]=(t[o].c[i+j]+t[ls].c[i]*t[rs].c[j]%mod)%mod;
    }
    inline void pushdown(int o) {
        if (t[o].revv) rev(ls),rev(rs),t[o].revv=0;
        if (t[o].addv) add(ls,t[o].addv),add(rs,t[o].addv),t[o].addv=0;
    }

    inline void build(int o,int l,int r) {
        t[o].len=r-l+1;
        if (l==r) {
            t[o].c[0]=1,t[o].c[1]=(a[l]%mod+mod)%mod;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(o);
    }
    
    inline void update(int o,int l,int r,int ql,int qr,int v) {
        if (ql<=l&&r<=qr) { add(o,v); return; }
        int mid=(l+r)>>1; pushdown(o);
        if (ql<=mid) update(ls,l,mid,ql,qr,v);
        if (qr>mid) update(rs,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline void reverse(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) { rev(o); return; }
        int mid=(l+r)>>1; pushdown(o);
        if (ql<=mid) reverse(ls,l,mid,ql,qr);
        if (qr>mid) reverse(rs,mid+1,r,ql,qr);
        pushup(o);
    }
    inline node query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return t[o];
        int mid=(l+r)>>1; pushdown(o);
        if (qr<=mid) return query(ls,l,mid,ql,qr);
        else if (ql>mid) return query(rs,mid+1,r,ql,qr);
        else return merge(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
    }
    
#undef ls
#undef rs
    
} T;

int main() {
    int n,q; scanf("%d%d",&n,&q);
    for (re int i=1;i<=n;++i) scanf("%d",&a[i]);

    C[0][0]=1;
    for (re int i=1;i<=n;++i) {
        C[i][0]=1;
        for (re int j=1;j<=20&&j<=i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    T.build(1,1,n);
    
    while (q--) {
        char op[3]; scanf("%s",op);
        int a,b,c;
        if (op[0]=='I') {
            scanf("%d%d%d",&a,&b,&c);
            c=(c%mod+mod)%mod;
            T.update(1,1,n,a,b,c);
        }
        else if (op[0]=='R') {
            scanf("%d%d",&a,&b);
            T.reverse(1,1,n,a,b);
        }
        else if (op[0]=='Q') {
            scanf("%d%d%d",&a,&b,&c);
            printf("%lld\n",T.query(1,1,n,a,b).c[c]);
        }
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 07 PM

2 条评论

  1. smy

    清华集训爷%%%

    1. M_sea
      @smy

      不是您吗%%%%%

发表评论