平衡树维护序列的老题。之前用SMT写过，不过在bzoj上就tle了。splay大法好。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
#define readStr(_s_) { \
char* _i_ = _s_; \
while (!islower(_d_ = getchar())); \
while ((*(_i_ ++) = _d_), islower(_d_ = getchar())); \
*(_i_) = 0; \
}
#define _l (long long int)
const int maxn = 300009;
const int mod = 20130426;
struct node {
int ls, rs, pt, sz;
int val, mul, add;
};
struct splay_tree {
node t[maxn];
int cr, tn;
void init() {
t[0]. sz = 0;
t[0]. val = 0;
tn = 0;
cr = 0;
}
inline void update(int p) {
t[p]. sz = t[t[p]. ls]. sz + t[t[p]. rs]. sz + 1;
}
inline void pushDown(int p) {
if (t[p]. ls) {
t[t[p]. ls]. val = (_l t[t[p]. ls]. val * t[p]. mul + t[p]. add) % mod;
t[t[p]. ls]. mul = (_l t[t[p]. ls]. mul * t[p]. mul) % mod;
t[t[p]. ls]. add = (_l t[t[p]. ls]. add * t[p]. mul + t[p]. add) % mod;
}
if (t[p]. rs) {
t[t[p]. rs]. val = (_l t[t[p]. rs]. val * t[p]. mul + t[p]. add) % mod;
t[t[p]. rs]. mul = (_l t[t[p]. rs]. mul * t[p]. mul) % mod;
t[t[p]. rs]. add = (_l t[t[p]. rs]. add * t[p]. mul + t[p]. add) % mod;
}
t[p]. mul = 1;
t[p]. add = 0;
}
inline void lRot(int q) {
int p = t[q]. pt, a = t[p]. pt;
if (t[q]. rs)
t[t[q]. rs]. pt = p;
t[p]. ls = t[q]. rs;
t[q]. rs = p;
t[p]. pt = q;
t[q]. pt = a;
if (a) {
if (p == t[a]. ls)
t[a]. ls = q;
else
t[a]. rs = q;
}
update(p);
update(q);
}
inline void rRot(int q) {
int p = t[q]. pt, a = t[p]. pt;
if (t[q]. ls)
t[t[q]. ls]. pt = p;
t[p]. rs = t[q]. ls;
t[q]. ls = p;
t[p]. pt = q;
t[q]. pt = a;
if (a) {
if (p == t[a]. ls)
t[a]. ls = q;
else
t[a]. rs = q;
}
update(p);
update(q);
}
void upath(int q) {
for (; q; q = t[q]. pt)
update(q);
}
void dpath(int q) {
static int stc[maxn];
int tst = 0;
for (int u = q; u; u = t[u]. pt)
stc[++ tst] = u;
for (; tst; -- tst) {
update(stc[tst]);
pushDown(stc[tst]);
}
}
void splay(int q) {
dpath(q);
while (t[q]. pt) {
int p = t[q]. pt, a = t[p]. pt;
if (!a || !t[a]. pt) {
if (q == t[p]. ls)
lRot(q);
else
rRot(q);
}
else {
if (p == t[a]. ls) {
if (q == t[p]. ls)
lRot(p), lRot(q);
else
rRot(q), lRot(q);
}
else {
if (q == t[p]. ls)
lRot(q), rRot(q);
else
rRot(p), rRot(q);
}
}
}
cr = q;
}
int kth(int k) {
int p = cr;
while (p)
if (t[t[p]. ls]. sz == k)
break;
else if (t[t[p]. ls]. sz > k)
p = t[p]. ls;
else
k -= t[t[p]. ls]. sz + 1, p = t[p]. rs;
return p;
}
int build(int l, int r) {
if (l > r)
return 0;
int p = ++ tn, mid = (l + r) >> 1;
t[p]. val = 0;
t[p]. add = 0;
t[p]. mul = 1;
t[p]. ls = build(l, mid - 1);
if (t[p]. ls)
t[t[p]. ls]. pt = p;
t[p]. rs = build(mid + 1, r);
if (t[p]. rs)
t[t[p]. rs]. pt = p;
update(p);
return p;
}
int getRange(int l, int r) {
if (!cr)
cr = build(0, r);
if (r >= t[cr]. sz) {
int x = kth(t[cr]. sz - 1);
int z = build(t[cr]. sz, r);
splay(x);
pushDown(x);
t[x]. rs = z;
t[z]. pt = x;
update(x);
}
if (!l && r == t[cr]. sz - 1)
return cr;
else if (!l) {
int x = kth(r + 1);
splay(x);
return t[x]. ls;
}
else if (r == t[cr]. sz - 1) {
int x = kth(l - 1);
splay(x);
return t[x]. rs;
}
else {
int x = kth(l - 1);
int y = kth(r + 1);
splay(x);
splay(y);
return t[x]. rs;
}
}
void add(int p, int v) {
dpath(p);
t[p]. val = (_l t[p]. val + v) % mod;
t[p]. add = (_l t[p]. add + v) % mod;
}
void mul(int p, int v) {
dpath(p);
t[p]. val = _l t[p]. val * v % mod;
t[p]. add = _l t[p]. add * v % mod;
t[p]. mul = _l t[p]. mul * v % mod;
}
int rmvKth(int k) {
int x = getRange(k, k);
if (t[cr]. sz == 1)
return cr = 0, t[x]. val;
dpath(x);
int ret = t[x]. val;
if (t[x]. pt) {
if (x == t[t[x]. pt]. ls)
t[t[x]. pt]. ls = 0;
else
t[t[x]. pt]. rs = 0;
upath(t[x]. pt);
}
return ret;
}
void ins(int k) {
int x = getRange(k, k);
while (t[x]. ls)
x = t[x]. ls;
dpath(x);
++ tn;
t[tn]. ls = 0;
t[tn]. rs = 0;
t[tn]. pt = x;
t[tn]. sz = 1;
t[tn]. val = 0;
t[tn]. mul = 1;
t[tn]. add = 0;
t[x]. ls = tn;
upath(tn);
splay(tn);
}
int dfsAns(int p, int& x, int x0) {
int ret = 0;
pushDown(p);
if (t[p]. ls)
ret = dfsAns(t[p]. ls, x, x0);
ret = (_l ret + _l x * t[p]. val) % mod;
x = _l x * x0 % mod;
if (t[p]. rs)
ret = (ret + dfsAns(t[p]. rs, x, x0)) % mod;
return ret;
}
int getAns(int x) {
int tmp = 1;
return dfsAns(cr, tmp, x);
}
};
int n;
splay_tree t;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
t. init();
readInt(n);
while (n --) {
char opt[7];
int l, r, v;
readStr(opt);
if (opt[0] == 'm' && opt[3] == 0) {
readInt(l);
readInt(r);
readInt(v);
int x = t. getRange(l, r);
t. mul(x, v);
}
else if (opt[0] == 'a') {
readInt(l);
readInt(r);
readInt(v);
int x = t. getRange(l, r);
t. add(x, v);
}
else if (opt[3] == 'x') {
readInt(l);
readInt(r);
int v = t. rmvKth(r);
int x = t. getRange(r, r);
t. add(x, v);
t. ins(l);
}
else {
readInt(v);
printf("%d\n", t. getAns(v));
}
}
}