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
| void update(int i){
int pos=n+1;
while(!q.empty()){
node now=q.back();q.pop_back();
int l=now.l,r=now.r,j=now.j;
if(f[i]+w(i,l)<=f[j]+w(j,l)){
pos=l;
continue;
}
if(f[i]+w(i,r)>f[j]+w(j,r)){
q.push_back(now);
break;
}
int mid;
while(l+1<r){
mid=l+r>>1;
if(f[i]+w(i,mid)<=f[j]+w(j,mid))r=mid;
else l=mid;
}
if(f[i]+w(i,l)<=f[j]+w(j,l))pos=l;
else pos=r;
now.r=pos-1;
q.push_back(now);
break;
}
if(pos<=n)
q.push_back((node){pos,n,i});
}
void work(){
q.clear(),q1.clear();
q.push_back((node){1,n,0});
for(int i=1;i<=n;++i){
node now=q.front();q.pop_fro();
if(now.r==i)q1.push_node(now);
else{
q.push_fro((node){i+1,now.r,now.j});
q1.push_node((node){now.l,i,now.j});
}
int j=q1.back().j;
f[i]=f[j]+w(j,i);
if(i!=n)
update(i);
}
}
|
