bzoj 2962 序列操作(线段树)

题外话

做这道题我整个人都非常的绝望，推了一会发现是线段树裸题，然后调了N久一直是WA

情况是这样的

开始WA的几百毫秒的都是由于我比较SB造成的，可是跑了10几秒的程序我查了N久也查不出错

$最后灵机一动把50000改成60000就过了，也不知道为啥$T_T

Description

$一个长度为n的序列，有3种操作$

$1:区间加c$

$2:区间取为相反数$

$3:询问区间中选择c个数相乘的所有方案的和mod 19940417的值$

Solution

$这个操作3非常鬼畜，似乎没啥好的办法，但是仔细推导一番会发现这个东西其实是可以区间合并的$

$用f[i]表示选i个数所有方案和，rt.f[i]=\sum_{j=0}^{i}ls.f[j]*rs.f[i-j]$

$然后注意一点f[0] = 1$

$对于第一种操作加k我们发现对答案f[i]会变为\sum_{j=0}^{i}f[j]*C_{n-j}^{i} * k^{i-j}$(想一想为什么)

$对于第二种操作取反，我们发现只有当c为奇数时答案会取反，这个也很好搞$

$然后就是打两个标记reverse和add的线段树辣，注意处理标记的顺序$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
const int N = 60050, M = 19940417;
int a[N], b[25], c[N][25], add[N << 2], rev[N << 2];
struct node {
    int f[25];
}p[N << 2];
inline int read(int &t) {
    int f = 1;char c;
    while (c = getchar(), c < ‘0‘ || c > ‘9‘) if (c == ‘-‘) f = -1;
    t = c - ‘0‘;
    while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) t = t * 10 + c - ‘0‘;
    t *= f;
}
inline void U(int &x, int y) {
    x += y;
    if (x >= M) x -= M;
    if (x < 0)  x += M;
}
void calc(int rt, int l, int r, int x) {
    for (int i = 1; i <= 20; ++i) {
        int t = 0, tx = 1;
        for (int j = i; j >= 0; --j) {
            U(t, (LL)p[rt].f[j] * c[r - l + 1 - j][i - j] % M * tx % M);
            tx = (LL)tx * x % M;
        }
        b[i] = t;
    }   
    for (int i = 1; i <= 20; ++i)   p[rt].f[i] = b[i];
}
void down(int rt, int l, int r) {
    if (rev[rt]) {
        rev[ls] ^= 1, rev[rs] ^= 1;
        for (int i = 1; i <= 20; i += 2)    p[ls].f[i] = (M - p[ls].f[i]) % M;
        for (int i = 1; i <= 20; i += 2)    p[rs].f[i] = (M - p[rs].f[i]) % M;
        add[ls] = (M - add[ls]) % M, add[rs] = (M - add[rs]) % M;
        rev[rt] = 0;
    }
    if (add[rt]) {
        int mid = l + r >> 1;
        U(add[ls], add[rt]), U(add[rs], add[rt]);
        calc(ls, l, mid, add[rt]), calc(rs, mid + 1, r, add[rt]);
        add[rt] = 0;
    }
} 
void up(int rt) {
    for (int i = 1; i <= 20; ++i)   p[rt].f[i] = 0;
    for (int i = 0; i <= 20; ++i)   
        for (int j = 0; i + j <= 20; ++j) {
            if (i + j == 0) continue;
            U(p[rt].f[i + j], (LL)p[ls].f[i] * p[rs].f[j] % M);
        }
}
void build(int rt, int l, int r) {
    p[rt].f[0] = 1;
    if (l == r) {
        p[rt].f[1] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    up(rt);
}
void reverse(int rt, int l, int r, int L, int R) {
    if (L <= l && R >= r) {
        rev[rt] ^= 1;
        add[rt] = (M - add[rt]) % M;
        for (int i = 1; i <= 20; i += 2) p[rt].f[i] = (M - p[rt].f[i]) % M;
        return;
    }
    down(rt, l, r);
    int mid = l + r >> 1;
    if (L <= mid)   reverse(ls, l, mid, L, R);
    if (R > mid)    reverse(rs, mid + 1, r, L, R);
    up(rt);
}
void inc(int rt, int l, int r, int L, int R, int x) {
    if (L <= l && R >= r) {
        U(add[rt], x);
        calc(rt, l, r, x);
        return;
    }
    int mid = l + r >> 1;
    down(rt, l, r);
    if (L <= mid)   inc(ls, l, mid, L, R, x);
    if (R > mid)    inc(rs, mid + 1, r, L, R, x);
    up(rt);
}
node ask(int rt, int l, int r, int L, int R) {
    if (L <= l && R >= r) {
        return p[rt];
    }
    down(rt, l, r);
    int mid = l + r >> 1;
    node t, t1, t2;
    if (L > mid)    t = ask(rs, mid + 1, r, L, R);
    else if (R <= mid)  t = ask(ls, l, mid, L, R);
    else {
        t.f[0] = 1;
        for (int i = 1; i <= 20; ++i)   t.f[i] = 0;
        t1 = ask(ls, l, mid, L, mid), t2 = ask(rs, mid + 1, r, mid + 1, R);
        for (int i = 0; i <= 20; ++i)
            for (int j = 0; j + i <= 20; ++j) {
                if (i + j == 0) continue;
                U(t.f[i + j], (LL)t1.f[i] * t2.f[j] % M);
            }
    }   
    return t;
}   
int main() {
    int n, q;
    read(n), read(q);
    for (int i = 0; i <= n; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
    }
    for (int i = 1; i <= n; ++i)    read(a[i]), a[i] = (a[i] % M + M) % M;
    build(1, 1, n);
    char s[5];
    int x, y, z;
    while (q--) {
        scanf("%s", s);
        if (s[0] == ‘I‘) {
            read(x), read(y), read(z);
            z = (z % M + M) % M;
            inc(1, 1, n, x, y, z);
        }
        else if (s[0] == ‘R‘) {
            read(x), read(y);
            reverse(1, 1, n, x, y);
        }
        else {
            read(x), read(y), read(z);
            z = (z % M + M) % M;
            node t = ask(1, 1, n, x, y);
            printf("%d\n", t.f[z] % M);
        }
    }
    return 0;
}