隐藏
「bzoj2158」Crash的旅行计划 - 分类讨论+线段树/平衡树 | Bill Yang's Blog
0%

「bzoj2158」Crash的旅行计划 - 分类讨论+线段树/平衡树

题目大意

    过不了多久,Crash就要迎来他朝思暮想的暑假。在这个暑假里,他计划着到火星上旅游。在火星上有$N$个旅游景点,Crash用$1$至$N$这$N$个正整数对这些景点标号。旅游景点之间通过双向道路相连。由于火星的环境和地球有很大的差异,建立道路的成本也相对较高。为了节约成本,只有$N-1$条道路连接着这些旅游景点,不过可以保证任何两个不同的旅游景点都通过路径相连。
    Crash预先在互联网上查阅了这些景点的信息,根据网上的介绍,他对每个景点都有一个印象值,这个印象值为一个整数。在这个旅行中,他会选择一个景点作为旅行的开始,并沿着存在的道路到达其他景点游玩。为了使旅行不显得乏味,Crash不会经过同一个景点超过一次。Crash还给这次旅行定义了一个快乐指数,也就是他经过的所有景点的印象值之和。
    不过Crash是个奇怪的小朋友,他对于景点的印象值会发生改变,并且他也没有决定好应该从哪个景点开始旅行。因此他希望你能写一个程序帮他完成一个简单的任务:根据当前他对每个景点的印象值,计算从某个景点开始旅行所能获得的最大的快乐指数。
    测试数据分为$ABC$三类,对于所有的测试数据都满足:在任何时候一个景点印象值的绝对值不超过$10000$,并且输入的道路一定能满足题目描述的要求,即使得任意两个不同的景点都能通过路径相连。
    对于$A$类数据(占20%的分数)满足:$N$和指令的条数都不超过$1000$。
    对于$B$类数据(占40%的分数)满足:$N$和指令的条数都不超过$100000$,且输入的第$i$条道路,连接着$i$号景点和$i+1$号景点(详见样例2)。
    对于$C$类数据(占40%的分数)满足:$N$和指令的条数都不超过$100000$,且任何一个景点到$1$号景点需要通过的道路条数不超过$40$。


题目分析

强行题,根据数据分三类讨论。

对于A类数据,每次修改$O(1)$修改,询问暴力Dfs。
对于B类数据,呈单链形态,使用线段树维护最大前缀和与最大后缀和,每次查询询问当前位置前的最大后缀和与当前位置后的最大前缀和即可。
对于C类数据,有很多做法。

method A by xyj

因为树高只有$40$,不妨枚举最长链的$lca$,故要求:

因为$lca$已知,其实只需查询$\max\lbrace dist[u]+dist[v]\rbrace$,其中$u,v$来自不同子树。
这可以使用线段树维护Dfs序。

method B by achen

因为树高只有$40$,故每个结点维护其儿子最大的$f$值,即针对A类数据的递推值。

每个结点开一个堆,修改时从$x$爬树到$1$,对于路径上每个点,往堆中插入新值,并给原来的打上删除标记,若以后遇到堆顶有标记直接弹掉。
询问的时候同样向上爬树,询问子树的路径+经过的路径最大值即可,如图,求出$sum+max$的最大值即可。

method C by Bill

类似method B,但是智障的我肯定想不到延迟删除标记啦。
于是智障的敲了一个treap。
调成智障,跑得居然最快
我永远喜欢treap,splay一点也不好用


代码

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
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=100005;

char opt[maxn];
int x[maxn],y[maxn];
LL n,a[maxn];
vector<int>edges[maxn];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

namespace SolveA {
LL f[maxn];

void Dfs(int Now,int fa) {
f[Now]=0;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs(Next,Now);
f[Now]=max(f[Now],f[Next]);
}
f[Now]+=a[Now];
}

void solve() {
for(int i=1; opt[i]!='D'; i++) {
if(opt[i]=='C')a[x[i]]=y[i];
else {
Dfs(x[i],0);
printf("%lld\n",f[x[i]]);
}
}
}
}

namespace SolveB {
struct Segment_Tree {
struct Tree {
int left,right;
LL lmax,rmax,sum;
Tree(int l=0,int r=0,LL lm=-LLONG_MAX/2,LL rm=-LLONG_MAX/2,LL s=0):left(l),right(r),lmax(lm),rmax(rm),sum(s) {}
} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right,LL* a) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index]=Tree(Left,Right,a[Left],a[Left],a[Left]);
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,a);
build(rs,mid+1,Right,a);
push_up(index);
}
Tree merge(Tree l,Tree r) {
Tree ans;
ans.sum=l.sum+r.sum;
ans.lmax=max(l.lmax,l.sum+r.lmax);
ans.rmax=max(r.rmax,r.sum+l.rmax);
return ans;
}
void push_up(int index) {
int l=tree[index].left,r=tree[index].right;
tree[index]=merge(tree[ls],tree[rs]);
tree[index].left=l,tree[index].right=r;
}
void modify(int index,int target,LL val) {
if(target<tree[index].left||target>tree[index].right)return;
if(tree[index].left==tree[index].right) {
tree[index]=Tree(tree[index].left,tree[index].right,val,val,val);
return;
}
modify(ls,target,val);
modify(rs,target,val);
push_up(index);
}
Tree query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return Tree();
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index];
return merge(query(ls,Left,Right),query(rs,Left,Right));
}
} st;

void solve() {
st.build(1,1,n,a);
for(int i=1; opt[i]!='D'; i++) {
if(opt[i]=='C')st.modify(1,x[i],y[i]);
else {
Segment_Tree::Tree l=st.query(1,1,x[i]),r=st.query(1,x[i],n);
printf("%lld\n",max(l.rmax,r.lmax));
}
}
}
}

#undef ls
#undef rs

namespace SolveC {
struct Tree {
int child[2],size;
int d;
LL val;
} tree[maxn];

int cnt,num[maxn];
LL ta[maxn];

struct Treap {
int root;
#define d(x) tree[x].d
#define val(x) tree[x].val
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define root(x) tree[x].root
#define size(x) tree[x].size
void push_up(int index) {
int ls=ls(index),rs=rs(index);
size(index)=size(ls)+size(rs)+1;
}
void newnode(int now,LL val) {
val(now)=val;
d(now)=rand()*rand()%maxn;
size(now)=1;
ls(now)=rs(now)=0;
}
void rotate(int& index,bool side) {
int son=tree[index].child[side^1];
tree[index].child[side^1]=tree[son].child[side];
tree[son].child[side]=index;
push_up(index);
push_up(son);
index=son;
}
void insert(int& index,int num,LL val) {
if(!index) {
newnode(num,val);
index=num;
return;
}
bool side=val>val(index)||(val==val(index)&&num>index);
int &son=tree[index].child[side];
insert(son,num,val);
size(index)++;
if(d(index)<d(son))rotate(index,side^1);
}
void dfs(int index) {
if(!index)return;
if(ls(index))dfs(ls(index));
ta[++cnt]=val(index);
num[cnt]=index;
if(rs(index))dfs(rs(index));
}
int build(int Left,int Right) {
if(Left>Right)return 0;
int mid=(Left+Right)>>1,now=num[mid];
newnode(now,ta[mid]);
ls(now)=build(Left,mid-1);
rs(now)=build(mid+1,Right);
push_up(now);
return now;
}
int rebuild(int index) {
cnt=0;
dfs(ls(index));
dfs(rs(index));
int pos=build(1,cnt);
return pos;
}
void remove(int index) {
int now=root,father;
bool side;
while(val(now)!=val(index)||now!=index) {
father=now;
size(now)--;
if(val(now)>val(index)||(val(now)==val(index)&&now>index))now=ls(now),side=0;
else now=rs(now),side=1;
}
int pos=rebuild(now);
if(now!=root)tree[father].child[side]=pos;
else root=pos;
}
int kth(int rank) {
int now=root;
while(now>0&&rank>=0) {
if(rs(now)&&size(rs(now))>=rank)now=rs(now);
else {
if(rank<=size(rs(now))+1)return now;
rank-=size(rs(now))+1;
now=ls(now);
}
}
return -1;
}
} treap[maxn];

int father[maxn];
LL f[maxn];

void Dfs(int Now,int fa) {
f[Now]=0;
father[Now]=fa;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs(Next,Now);
treap[Now].insert(treap[Now].root,Next,f[Next]);
f[Now]=max(f[Now],f[Next]);
}
f[Now]+=a[Now];
}

void Modify(int Now,LL v) {
a[Now]=v;
int from;
while(true) {
LL tmp=treap[Now].kth(1);
if(tmp==-1)f[Now]=a[Now];
else f[Now]=max(0ll,f[tmp])+a[Now];
from=Now;
Now=father[Now];
if(!Now)break;
treap[Now].remove(from);
treap[Now].insert(treap[Now].root,from,f[from]);
}
}

LL Query(int Now) {
int from=0;
LL sum=a[Now],ans=-LLONG_MAX/2;
while(Now) {
int tmp=treap[Now].kth(1);
if(tmp==-1)ans=max(ans,sum);
else if(tmp!=from)ans=max(ans,max(0ll,f[tmp])+sum);
else {
tmp=treap[Now].kth(2);
if(~tmp)ans=max(ans,max(0ll,f[tmp])+sum);
else ans=max(ans,sum);
}
from=Now;
Now=father[Now];
sum+=a[Now];
}
return ans;
}

void solve() {
srand(time(NULL));
Dfs(1,0);
for(int i=1; opt[i]!='D'; i++) {
if(opt[i]=='C')Modify(x[i],y[i]);
else printf("%lld\n",Query(x[i]));
}
}
}

int main() {
char type=' ';
while(!isalpha(type))type=getchar();
n=Get_Int();
int m=Get_Int(),L=Get_Int(),now=Get_Int(),A=Get_Int(),B=Get_Int(),Q=Get_Int();
for(int i=1; i<=n; i++) {
now=(now*A+B)%Q;
int tmp=now%10000;
now=(now*A+B)%Q;
if(now*2<Q)tmp*=-1;
a[i]=tmp;
}
for(int i=1; i<n; i++) {
now=(now*A+B)%Q;
int tmp=i<L?i:L;
int x=i-now%tmp,y=i+1;
AddEdge(x,y);
AddEdge(y,x);
}
for(int i=1; i<m; i++) {
now=(now*A+B)%Q;
if(now*3<Q) {
now=(now*A+B)%Q;
opt[i]='Q';
x[i]=now%n+1;
} else {
now=(now*A+B)%Q;
int tmp=now%10000;
now=(now*A+B)%Q;
if(now*2<Q)tmp*=-1;
now=(now*A+B)%Q;
opt[i]='C';
x[i]=now%n+1;
y[i]=tmp;
}
}
opt[m]='D';
if(type=='A')SolveA::solve();
else if(type=='B')SolveB::solve();
else SolveC::solve();
return 0;
}
姥爷们赏瓶冰阔落吧~