```cpp
#include <bits/stdc++.h>
#include <random>
using namespace std;
typedef long long ll;
const ll P = 20130426;
#define self tr[p]
#define lson tr[tr[p].ls]
#define rson tr[tr[p].rs]
mt19937 rnd(time(0));
struct Node {
ll val;
ll add, mul;
int ls, rs;
int pri;
int siz;
} tr[100005];
int tcn;
int root;
int NewNode() {
int p = ++tcn;
self.add = self.val = 0;
self.ls = self.rs = 0;
self.mul = 1;
self.siz = 1;
self.pri = rnd();
return p;
}
int NewNode(int val) {
int p = NewNode();
self.val = val;
return p;
}
void Pushup(int p) {
self.siz = lson.siz + rson.siz + 1;
}
void Pushdown(int p) {
if (self.add || self.mul != 1) {
if (self.ls) {
lson.add = lson.add * self.mul % P;
lson.add = (lson.add + self.add) % P;
lson.mul = lson.mul * self.mul % P;
lson.val = (lson.val * self.mul % P + self.add) % P;
}
if (self.rs) {
rson.add = rson.add * self.mul % P;
rson.add = (rson.add + self.add) % P;
rson.mul = rson.mul * self.mul % P;
rson.val = (rson.val * self.mul % P + self.add) % P;
}
self.add = 0;
self.mul = 1;
}
}
void Split(int p, int rk, int &x, int &y) {
if (!p) {
x = y = 0;
return;
}
Pushdown(p);
if (lson.siz + 1 <= rk) {
x = p;
Split(self.rs, rk - lson.siz - 1, self.rs, y);
}
else {
y = p;
Split(self.ls, rk, x, self.ls);
}
Pushup(p);
}
int Merge(int x, int y) {
if (!x || !y) return x | y;
if (tr[x].pri >= tr[y].pri) {
Pushdown(x);
tr[x].rs = Merge(tr[x].rs, y);
Pushup(x);
return x;
}
else {
Pushdown(y);
tr[y].ls = Merge(x, tr[y].ls);
Pushup(y);
return y;
}
}
int GetVal(int rk) {
int x = 0, y = 0, z = 0;
Split(root, rk, x, z);
Split(x, rk - 1, x, y);
ll res = tr[y].val;
root = Merge(Merge(x, y), z);
return res;
}
void Insert(int rk, int val) {
int x = 0, y = 0;
int p = NewNode();
self.val = val;
Split(root, rk, x, y);
root = Merge(Merge(x, p), y);
}
void Delete(int rk) {
int x = 0, y = 0, z = 0;
Split(root, rk, x, z);
Split(x, rk - 1, x, y);
y = Merge(tr[y].ls, tr[y].rs);
root = Merge(Merge(x, y), z);
}
void Add(int l, int r, int w) {
int x = 0, y = 0, z = 0;
Split(root, r, x, z);
Split(x, l - 1, x, y);
tr[y].add = (tr[y].add + w) % P;
tr[y].val = (tr[y].val + w) % P;
root = Merge(Merge(x, y), z);
}
void Mul(int l, int r, int w) {
int x = 0, y = 0, z = 0;
Split(root, r, x, z);
Split(x, l - 1, x, y);
tr[y].mul = tr[y].mul * w % P;
tr[y].add = tr[y].add * w % P;
tr[y].val = tr[y].val * w % P;
root = Merge(Merge(x, y), z);
}
void MulX(int l, int r) {
ll t = GetVal(r);
Delete(r);
Insert(l - 1, 0);
Add(r + 1, r + 1, t);
}
ll v;
int l, r, w;
ll Query(int p) {
if (!p) return 0;
ll res = 0;
Pushdown(p);
res += Query(self.ls);
res += self.val * v % P;
v = v * w % P;
res %= P;
res += Query(self.rs);
res %= P;
return res;
}
void Print(int p) {
if (!p) return;
Pushdown(p);
Print(self.ls);
printf("%d ", self.val);
Print(self.rs);
if (p == root) {
putchar('\n');
}
}
int n;
char op[15];
int main() {
scanf("%d", &n);
for (int i = 0; i <= 100001; i++) Insert(0, 0);
while (n--) {
scanf("%s", op + 1);
if (!strcmp(op + 1, "mul")) {
scanf("%d%d%d", &l, &r, &w);
w %= P;
Mul(l + 1, r + 1, w);
}
else if (!strcmp(op + 1, "add")) {
scanf("%d%d%d", &l, &r, &w);
w %= P;
Add(l + 1, r + 1, w);
}
else if (!strcmp(op + 1, "mulx")) {
scanf("%d%d", &l, &r);
MulX(l + 1, r + 1);
}
else {
scanf("%d", &w);
w %= P;
v = 1;
printf("%lld\n", Query(root));
}
// Print(root);
}
return 0;
}
```
by 251Sec @ 2023-01-09 10:35:00
开 O2 变成 RE 了
by 251Sec @ 2023-01-09 10:47:22
数组开两倍过了
by 251Sec @ 2023-01-09 10:48:27