「SCOI2013」多项式的运算-Splay

维护一个动态的关于$x$的无穷多项式 ,这个多项式初始时对于所有$i$有$a_i = 0$

$f(x)=a_0x^0+a_1x^1+a_2x^2…$
操作者可以进行四种操作:

  • mul L R V表示将 $x^L$ 到 $x^R$ 这些项的系数乘上某个定值$v$;

  • add L R V表示将$x^L$ 到 $x^R $这些项的系数加上某个定值$v$;

  • mulx L R表示将$x^L$ 到 $x^R$ 这些项乘上x变量;

  • query V求$f(v)$的值。

操作集中在前三种,第四种操作不会出现超过$10$次。

链接

Luogu P3278

题解

Splay大毒瘤题。

前两个操作让我们想到线段树的模板,第三个操作如果从序列的角度来看就像是把一个序列向右移动,在把被冲掉的那一个位置加到原来的位数上去。

显然啊!同志们,这是送分题啊!Splay套套套…


  • add操作:提取区间,打标记,维护信息。

  • mul操作:提取区间,打标记,维护信息。

  • mulx操作:呃…先找到rank为l-1,l,r,r+1,r+2的节点。删除掉r+1号节点,把其值加到r上去,然后在l-1和l之间插入一个值为0的节点,维护信息。

注意:push_down操作先传muln,再传addn。

打标记几乎同线段树模板,就不说了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <cstdio>
#include <unistd.h>
#include <cctype>
#define ll long long
using namespace std;

const int MAXN = 210000;
const ll p = 20130426LL;

namespace fast_io {
//...
}using namespace fast_io;

inline void mod(ll &x){x %= p;}

struct Splay{
ll val[MAXN],addn[MAXN],muln[MAXN];
int f[MAXN],c[MAXN][2],siz[MAXN],tot,root;
int newnode(int v = 0){
val[++tot] = v;
siz[tot] = 1;
addn[tot] = 0,muln[tot] = 1;
return tot;
}
void add(int x,int num){
if(!x) return;
addn[x] += num,val[x] += num;
mod(val[x]),mod(addn[x]);
}
void mul(int x,int num){
if(!x) return;
muln[x] *= num,addn[x] *= num,val[x] *= num;
mod(addn[x]),mod(muln[x]),mod(val[x]);
}
void push_down(int x){
if(!x) return;
if(muln[x]!=1){
mul(c[x][0],muln[x]);
mul(c[x][1],muln[x]);
muln[x] = 1;
}
if(addn[x] != 0){
add(c[x][0],addn[x]);
add(c[x][1],addn[x]);
addn[x] = 0;
}
}
void push_up(int x){
if(!x) return;
siz[x] = siz[c[x][0]] + siz[c[x][1]] + 1;
}
void rotate(int x){
int y = f[x],z = f[y],t = (c[y][1]==x),w = c[x][1-t];
push_down(y),push_down(x);
f[x] = z;f[y] = x;
if(w) f[w] = y;
c[x][1-t] = y,c[y][t] = w;
if(z) c[z][c[z][1]==y] = x;
push_up(y),push_up(x);
if(!f[x]) root = x;
}
void splay(int x,int target = 0){
while(f[x]!=target){
int y = f[x],z = f[y];
if(z!=target)
(c[z][1]==y) ^ (c[y][1]==x)?rotate(x):rotate(y);
rotate(x);
}
}
int qrank(int r){
int x = root;
while(2333){
if(r <= siz[c[x][0]])
x = c[x][0];
else if(r == siz[c[x][0]] + 1)
break;
else
r -= siz[c[x][0]] + 1,x = c[x][1];
}
return x;
}
int __build(int l,int r,int fa){
if(l > r) return 0;
int mid = (l+r)>>1;
int x = newnode();
f[x] = fa;
c[x][0] = __build(l,mid-1,x);
c[x][1] = __build(mid+1,r,x);
push_up(x);
return x;
}
void build(int num){
root = __build(1,num,0);
}
void __output(int x,ll *a){
if(!x) return;
push_down(x);
__output(c[x][0],a);
a += siz[c[x][0]],*a = val[x];
__output(c[x][1],a+1);
}
void output(ll *a){
__output(root,a);
}
void add(int l,int r,int num){
int lb = qrank(l),rb = qrank(r+2);
splay(lb),splay(rb,lb);
add(c[rb][0],num);
push_up(rb),push_up(lb);
}
void mul(int l,int r,int num){
int lb = qrank(l),rb = qrank(r+2);
splay(lb),splay(rb,lb);
mul(c[rb][0],num);
push_up(rb),push_up(lb);
}
void mulx(int l,int r){
int x = qrank(l),y = qrank(l+1),z = qrank(r+1),a = qrank(r+2),b = qrank(r+3);
splay(z),splay(b,z);
c[b][0] = 0;push_up(b),push_up(z);
val[z] += val[a];
splay(x),splay(y,x);
c[y][0] = newnode(),f[c[y][0]] = y;
push_up(y),push_up(x);
}
}T;

int n,m = 110000;

ll query(ll v){
static ll o[MAXN];
T.output(o);
ll ans = 0;
for(int i = m;i>=1;i--){
ans = ans * v + o[i];
mod(ans);
}
return ans;
}


void init(){
read(n);
T.build(m+3);
}

void solve(){
char op[10];int l,r,v;
for(int i = 1;i<=n;i++){
read(op);
if(op[0] == 'q'){
read(v);
print(int(query(v))),print('\n');
}
else{
read(l),read(r);
if(op[3] == 'x')
T.mulx(l+1,r+1);
else{
read(v);
if(op[0] == 'm')
T.mul(l+1,r+1,v);
else if(op[0] == 'a')
T.add(l+1,r+1,v);
}
}
}
}

int main(){
init();
solve();
flush();
return 0;
}