[THUT2012]序列操作 题解
![[THUT2012]序列操作 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180223b.png)
题目地址：洛谷：【P4247】[清华集训]序列操作 – 洛谷、BZOJ：Problem 2962. — 序列操作
题目描述
有一个长度为n的序列，有三个操作：
I a b c表示将[a, b]这一段区间的元素集体增加c；R a b表示将[a, b]区间内所有元素变成相反数；Q a b c表示询问[a, b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。
输入输出格式
输入格式：
第一行两个数n, q表示序列长度和操作个数。
第二行n个非负整数，表示序列。
接下来q行每行输入一个操作I a b c或者R a b或者Q a b c，意义如题目描述。
输出格式：
对于每个询问，输出选出c个数相乘的所有方案的和mod 19940417的值。
输入输出样例
输入样例#1：
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
输出样例#1：
40 19940397
说明
样例说明：
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为3 \times 4+3 \times 4+4 \times 4=40。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为-2-4-5-4-5=-20。
数据范围：
对于100%的数据，n≤50000，q≤50000，初始序列的元素的绝对值≤109，保证[a, b]是一个合法区间，I操作中∣c∣≤109，Q操作中1≤c≤min(b−a+1, 20)。
题解
这个题里面有两种标记（相反数、区间加）和一种询问。我们分开来看。
标记与标记的应用
这里我们规定相反数的标记比加法标记优先级更高。试想，如果应用的顺序相反，可能会造成-a_i+add_i变成-(a_i+add_i)。
首先考虑区间信息的设置。应该记下本区间长度和一个f[21]数组，代表这个区间内对于每个c询问的答案。规定任意的f[0]为0。
如果要应用一个取相反数标记，应该将上述c为奇数时的情况的f值取相反数，因为偶数次相乘负号会抵消。
如果要应用一个区间加标记，思考对答案的改变，以f[15]这个值为例：
假如选择前15个值相乘，变化如下
[a_1, a_2, \cdots, a_{15}] \to [a_1 + c, a_2 + c, \cdots, a_{15} + c]
乘起来是这样的
f_{15} = C_{len-15}^0 \cdot c^0 \cdot f_{15} + C_{len-14}^1 \cdot c^1 \cdot f_{14} + C_{len-13}^2 \cdot c^2 \cdot f_{13} + \cdots + C_{len-0}^{15} \cdot c^{15} \cdot f_0
那我们就明白了，倒序求f值就好了。这里的C可以开始的时候预处理打个大表，空间是够的。区间加标记应用对应的代码长这样
inline void add(Data &dat, LL x) {
for(int i = std::min(dat.len, 20ll); i >= 0; i--) {
LL t = x;
for(int j = i - 1; j >= 0; j--) {
dat.f[i] = (dat.f[i] + dat.f[j] * C[dat.len - j][i - j] % MO * t % MO) % MO;
dat.f[i] = (dat.f[i] + MO) % MO;
t = t * x % MO;
}
}
dat.toadd = (dat.toadd + x) % MO;
}
区间合并
重点是要计算f值。首先考虑大区间选若干个是可以拆成左边选若干个和右边选若干个乘在一起的，这样既然左右两边的答案都是一堆乘积加起来，两块直接乘在一起就相当于两两配对后加起来，因此我们合并的公式就是：
f_k = \sum_{i=0}^k fl_i \times fr_{k-i}
上面式子的fl是左儿子f值，fr是右儿子f值。两层循环加一下就好。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 50005, MO = 19940417;
LL n, q, a, b, c, C[MAXN][21], val[MAXN];
char op;
inline bool isop(char c) {
return c == 'I' || c == 'R' || c == 'Q';
}
inline char readop() {
char c = fgc();
while (!isop(c)) c = fgc();
return c;
}
inline void calc() {
C[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= std::min(i, 20); j++) {
C[i][j] += C[i - 1][j];
if(j - 1 >= 0) C[i][j] += C[i - 1][j - 1];
C[i][j] %= MO;
}
}
}
#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)
struct Data {
LL len, toadd, f[21];
bool torev;
} tree[MAXN << 2];
inline void merge(Data &rt, Data ls, Data rs) {
rt.len = ls.len + rs.len;
memset(rt.f, 0, sizeof(rt.f));
for(int i = 0; i <= std::min(ls.len, 20ll); i++) {
for(int j = 0; j <= std::min(rs.len, 20ll); j++) {
if(i + j <= 20) rt.f[i + j] = (rt.f[i + j] + ls.f[i] * rs.f[j] % MO) % MO;
}
}
}
inline void build(int o, int l, int r) {
if(l == r) {
tree[o].len = 1;
tree[o].f[0] = 1;
tree[o].f[1] = val[l];
return;
}
build(lch, l, mid);
build(rch, mid + 1, r);
merge(tree[o], tree[lch], tree[rch]);
}
inline void add(Data &dat, LL x) {
for(int i = std::min(dat.len, 20ll); i >= 0; i--) {
LL t = x;
for(int j = i - 1; j >= 0; j--) {
dat.f[i] = (dat.f[i] + dat.f[j] * C[dat.len - j][i - j] % MO * t % MO) % MO;
dat.f[i] = (dat.f[i] + MO) % MO;
t = t * x % MO;
}
}
dat.toadd = (dat.toadd + x) % MO;
}
inline void rev(Data &dat) {
for(int i = 0; i <= std::min(dat.len, 20ll); i++) {
if(i & 1) {
dat.f[i] = (-dat.f[i] % MO + MO) % MO;
}
}
dat.torev = !dat.torev;
dat.toadd = (-dat.toadd % MO + MO) % MO;
}
inline void pushdown(int o) {
if(tree[o].torev) {
rev(tree[lch]);
rev(tree[rch]);
tree[o].torev = false;
}
if(tree[o].toadd != 0) {
add(tree[lch], tree[o].toadd);
add(tree[rch], tree[o].toadd);
tree[o].toadd = 0;
}
}
inline void modifyI(int o, int l, int r, int ll, int rr, LL v) {
if(l == ll && r == rr) {
add(tree[o], v);
return;
}
pushdown(o);
if(rr <= mid) {
modifyI(lch, l, mid, ll, rr, v);
} else if(ll > mid) {
modifyI(rch, mid + 1, r, ll, rr, v);
} else {
modifyI(lch, l, mid, ll, mid, v);
modifyI(rch, mid + 1, r, mid + 1, rr, v);
}
merge(tree[o], tree[lch], tree[rch]);
}
inline void modifyR(int o, int l, int r, int ll, int rr) {
if(l == ll && r == rr) {
rev(tree[o]);
return;
}
pushdown(o);
if(rr <= mid) {
modifyR(lch, l, mid, ll, rr);
} else if(ll > mid) {
modifyR(rch, mid + 1, r, ll, rr);
} else {
modifyR(lch, l, mid, ll, mid);
modifyR(rch, mid + 1, r, mid + 1, rr);
}
merge(tree[o], tree[lch], tree[rch]);
}
inline Data query(int o, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) {
return tree[o];
}
pushdown(o);
if(rr <= mid) {
return query(lch, l, mid, ll, rr);
} else if(ll > mid) {
return query(rch, mid + 1, r, ll, rr);
} else {
Data res;
merge(res, query(lch, l, mid, ll, mid), query(rch, mid + 1, r, mid + 1, rr));
return res;
}
}
int main() {
n = readint();
q = readint();
calc();
for(int i = 1; i <= n; i++) {
val[i] = readint();
val[i] = (val[i] % MO + MO) % MO;
}
build(1, 1, n);
while(q--) {
op = readop();
if(op == 'I') {
a = readint();
b = readint();
c = readint();
c = (c % MO + MO) % MO;
modifyI(1, 1, n, a, b, c);
}
if(op == 'R') {
a = readint();
b = readint();
modifyR(1, 1, n, a, b);
}
if(op == 'Q') {
a = readint();
b = readint();
c = readint();
Data res = query(1, 1, n, a, b);
printf("%lld\n", res.f[c]);
}
}
return 0;
}
