BZOJ 1500 维修数列

维修数列!1.5days! # Link # Solution Splay模板题 ### 获得区间 设区间为\([l,r]\),则在Splay中找到l-1r+1的位置,将l-1\(Splay()\)到根,将r+1\(\rm Splay()\)到根节点的下方,则r+1的左子树即为相应的区间。即可对此区间进行相应操作。 ### 内存回收 建立类似队列的数据结构,存储可用的数组下标。 ### 最大子段和 //其它分治的数据结构都可以维护 对于每个节点代表的子树代表的区间\([l,r]\),维护从l开始向右扩展、r开始向左扩展的最大和以及该区间的最大子段和。对于每个非叶结点,求法为 \(lex=max(0,rson.lex,rson.sum+lson.lex)\) \(rex=max(0,lson.rex,lson.sum+rson.rex\) \(msub=max(lson.msub,rson.msub,lson.lex+v+rson.rex)\) # Tips 1. 对于\(Reverse()\)操作,每次\(down()\)将当前节点的rev域取反,而不是简单赋值为true 2. 对于\(down()\)操作,和线段树不同,必须在执行\(down(pos)\)时,将pos的标记下传给子节点,并把子节点的数据改对。

再做

访问的信息不能包含空节点。即使是Msub也要Split(1,TOL) 或者是在上传的时候特判

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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
using std::swap;
using std::max;
template <class T> inline T max(const T& a,const T& b,const T& c){return max(max(a,b),c);}
const int MAXN=500000+1,INF=1e9;
struct SplayNode
{
SplayNode *son[2],*fa;
int v,sz,
rx,lx,msub,sumv,//lx rx必须取
cover,rev;
int kind()
{
return fa->son[1]==this;
}
void same(int c)
{
if(!sz)
return;
cover=v=c;
sumv=sz*c;
lx=rx=msub=max(sumv,c);
}
void reverse()
{
if(!sz)
return;
rev^=1;
swap(son[0],son[1]);
swap(rx,lx);
}
void up()
{
sz=son[0]->sz+son[1]->sz+1;
sumv=son[0]->sumv+son[1]->sumv+v;
msub=max(son[0]->msub,
son[1]->msub,
max(0,son[0]->rx)+v+max(0,son[1]->lx));
lx=max(son[0]->lx,
son[0]->sumv+v+max(0,son[1]->lx));
rx=max(son[1]->rx,
son[1]->sumv+v+max(0,son[0]->rx));
}
void down()
{
if(cover!=INF)
{
son[0]->same(cover);
son[1]->same(cover);
cover=INF;
}
if(rev)
{
son[0]->reverse();
son[1]->reverse();
rev^=1;
}
}
}spl[MAXN],*null=spl,*pc=spl,*root;
void InitSplay()
{
null->fa=null->son[0]=null->son[1]=null;
null->sz=0;null->sumv=null->v=0;
null->lx=null->rx=null->msub=-INF;//check this out
null->cover=INF;null->rev=0;
}
SplayNode *S[MAXN],**top=S;
SplayNode *newSplayNode(int v)
{
SplayNode *cur;
if(top!=S)
cur=*top--;
else
cur=++pc;
cur->son[0]=cur->son[1]=cur->fa=null;
cur->v=cur->rx=cur->lx=cur->msub=cur->sumv=v;
cur->cover=INF;cur->rev=0;
cur->sz=1;
return cur;
}
void Rec(SplayNode *pos){*++top=pos;}
void uptoroot(SplayNode *pos)
{
if(pos==null)
return;
pos->up();
uptoroot(pos->fa);
}
SplayNode *Build(int L,int R,int *s)
{
if(L>R) return null;
int MID=L+R>>1;
SplayNode *cur=newSplayNode(s[MID]);
cur->son[0]=Build(L,MID-1,s);cur->son[0]->fa=cur;
cur->son[1]=Build(MID+1,R,s);cur->son[1]->fa=cur;
cur->up();
return cur;
}
void trans(SplayNode *pos)
{
SplayNode *f=pos->fa,*grf=f->fa;
int jud=pos->kind();
if(grf!=null)//f!=root)
grf->son[f->kind()]=pos;
pos->fa=grf;
pos->son[!jud]->fa=f;f->son[jud]=pos->son[!jud];
pos->son[!jud]=f;f->fa=pos;
f->up(),pos->up();
}
void Splay(SplayNode *pos,SplayNode *goal)
{
SplayNode *f;
while((f=pos->fa)!=goal)
{
if(f->fa!=goal)
trans(f->kind()==pos->kind()?f:pos);
trans(pos);
}
if(goal==null)
root=pos;
}
SplayNode *Kth(int K)
{
K++;
SplayNode *pos=root;
int d;
pos=root;
while(K)
{
pos->down();
if((d=pos->son[0]->sz+1)==K)
return pos;
if(d<K)
{
K-=d;
pos=pos->son[1];
}
else
pos=pos->son[0];
}
return 0;
}
SplayNode *Split(int l,int r)//返回区间父节点
{
SplayNode *pl=Kth(l-1),*pr=Kth(r+1);
Splay(pl,null);
Splay(pr,pl);
return pr;
}
void Insert(int pos,int n,int *s)
{
SplayNode *cur=Build(1,n,s),*p=Split(pos+1,pos);
p->son[0]=cur;cur->fa=p;
uptoroot(cur->fa);
}
void Del(SplayNode *p)
{
if(p==null)
return;
Del(p->son[0]);
Del(p->son[1]);
Rec(p);
}
void Delete(int l,int n)
{
int r=l+n-1;
SplayNode *p=Split(l,r)->son[0];
p->fa->son[p->kind()]=null;
uptoroot(p->fa);
Del(p);
}
void Cover(int l,int n,int c)
{
int r=l+n-1;
SplayNode *p=Split(l,r)->son[0];
p->same(c);
uptoroot(p->fa);//meixie....
}
void Reverse(int l,int n)
{
int r=l+n-1;
SplayNode *p=Split(l,r)->son[0];
p->reverse();
uptoroot(p->fa);
}
int Sum(int l,int n)
{
int r=l+n-1;
return Split(l,r)->son[0]->sumv;
}
int main()
{
InitSplay();
//freopen("input","r",stdin);
static int s[MAXN];
int n,m;red(n),red(m);
for(int i=2;i<=n+1;i++)
red(s[i]);
//s[0]=s[n+2]=-INF;
root=Build(1,n+2,s);
char opt[20];
int t1,t2,t3,t4;
for(int i=1;i<=m;i++)
{
scanf("%s",opt);
switch(opt[2])
{
case 'S'://ins
red(t1),red(t2);
for(int i=1;i<=t2;i++)
red(s[i]);
n+=t2;
Insert(t1,t2,s);
break;
case 'L'://del
red(t1),red(t2);
n-=t2;
Delete(t1,t2);
break;
case 'K'://msame
red(t1),red(t2),red(t3);
Cover(t1,t2,t3);
break;
case 'V'://rev
red(t1),red(t2);
Reverse(t1,t2);
break;
case 'T'://GET SUM
red(t1),red(t2);
printf("%d\n",Sum(t1,t2));
break;
case 'X':
printf("%d\n",Split(1,n)->son[0]->msub);
break;
}
}
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利