[Codevs 3306] 과일 언니 과일 거리 구경 Ⅲ 나무 사슬 분할

고치다됐어!좋아!많다맙소사!
선분 수 는 zkw 를 시도 해 보 았 으 니 수확 이 있 는 셈 이다.
주석

#include
#include
#include
#include
#include
using namespace std;
#define pb push_back 
const int inf=1047483647;
int n,m,fa[200010],top[200010],v[200010],w[200010],siz[200010],son[200010],f[1000010][4],ans,maxp,cntw,dep[200010],maxv,minv;
vector a[200010];
void init(){
	for (maxp=1;maxp<=n+2;maxp<<=1);
	f[maxp][0]=-inf;f[maxp][1]=inf;
	f[maxp*2-1][0]=-inf;f[maxp*2-1][1]=inf;
}
void dfs1(int ro){
	int y;
	siz[ro]=1;son[ro]=0;
	for (int i=0;isiz[son[ro]]) son[ro]=y;
} 
return ;
}
void dfs2(int ro){
int y;
if (ro>1) w[ro]=++cntw;
if (son[ro]) {
top[son[ro]]=top[ro];
dfs2(son[ro]);	
}
for (int i=0;i>=1;
for (;tmp>=1;tmp>>=1){
f[tmp][0]=max(f[tmp*2][0],f[tmp*2+1][0]);
f[tmp][1]=min(f[tmp*2][1],f[tmp*2+1][1]);
f[tmp][2]=max(f[tmp*2][0]-f[tmp*2+1][1],max(f[tmp*2][2],f[tmp*2+1][2]));
f[tmp][3]=max(f[tmp*2+1][0]-f[tmp*2][1],max(f[tmp*2][3],f[tmp*2+1][3]));
}
}
int zkw_query(int ty,int l,int r){
l=maxp+l-1;r=maxp+r+1;
int tmp,tmp1,tmp2;
if (ty==0) tmp=inf;
else tmp=-inf;
tmp1=-inf;tmp2=inf;
for (;r-l>1;l>>=1,r>>=1){
if (~l&1) ans=max(ans,f[l+1][2+ty]);
if (r&1) ans=max(ans,f[r-1][2+ty]);
if (ty==0) {
if (~l&1) {
tmp=min(tmp,f[l+1][1]);
ans=max(ans,tmp1-f[l+1][1]);
tmp1=max(tmp1,f[l+1][0]);
}
if (r&1) {
tmp=min(tmp,f[r-1][1]);
ans=max(ans,f[r-1][0]-tmp2);
tmp2=min(tmp2,f[r-1][1]);	
}
}
else {
if (r&1) {
tmp=max(tmp,f[r-1][0]);
ans=max(ans,tmp1-f[r-1][1]);
tmp1=max(tmp1,f[r-1][0]);
}
if (~l&1) {
tmp=max(tmp,f[l+1][0]);
ans=max(ans,f[l+1][0]-tmp2);
tmp2=min(tmp2,f[l+1][1]);	
}
}
if (~l&1) {
ans=max(ans,f[l+1][0]-minv);
ans=max(ans,maxv-f[l+1][1]);
}
if (r&1){
ans=max(ans,f[r-1][0]-minv);
ans=max(ans,maxv-f[r-1][1]);
}
}
ans=max(ans,tmp1-tmp2);
return tmp;
}
void query(int x,int y){
ans=0;maxv=-inf;minv=inf;
int d=0;
while (x!=y){
if (top[x]==top[y]){
if (dep[x]>dep[y]){
swap(x,y);d^=1;
}
if (d==0) minv=min(minv,zkw_query(0,w[x]+1,w[y]));
else maxv=max(maxv,zkw_query(1,w[x]+1,w[y]));
y=x;break;
}
if (dep[top[x]]>dep[top[y]]){
swap(x,y);d^=1;
}
if (top[y]==y){
if (d==0) minv=min(minv,v[y]);
else maxv=max(maxv,v[y]);
ans=max(ans,max(maxv-v[y],v[y]-minv));
y=fa[y];continue;
}
if (d==0) minv=min(minv,zkw_query(0,w[top[y]]+1,w[y]));
else maxv=max(maxv,zkw_query(1,w[top[y]]+1,w[y]));
y=top[y];
}
maxv=max(maxv,v[x]);minv=min(minv,v[x]);
ans=max(ans,maxv-minv);
}
int main(){
scanf("%d",&n);
init();
for (int i=1;i<=n;i++) scanf("%d",&v[i]);
for (int i=1;i<=n;i++) v[i]=-v[i];
int x,y,z;
for (int i=1;i