NOIP模拟赛20191030 Star Way To Heaven, God Knows, Lost My Music【Prim, 线段树后缀最大值(李超线段树), 可持久化栈(凸包)】

T1：Star Way To Heaven

做多了这种题很容易第一眼想到二分距离然后看上下是否连通，但是6000的n²log显然会T（我信仰了一发之后自己造大数据连1000都要跑3s+。。） 再仔细思考一下，答案需要满足小于这个距离的边不能使上下连通，那么至少需要多大的边才能使上下连通呢？最小生成树！上连到下经过的最大边就是我们的答案。O(n²)Prim即可。

这启示我们最小值最大除了二分还可以最小生成树。

---

T2：God Knows

如果把$p[i]$看做高度，最后答案删除的点一定是一个极长上升序列（任意两个$i<j$之间不存在$p[i]<p[k]<p[j]$）

那么就有了一个$O(n^2)$的DP，$f[i]$表示最后一个选的是$i$的最小代价，枚举$j$来转移，$j$要满足$p[j]<p[i]$且中间不存在介于$p[j]$到$p[i]$之间的高度，这可以通过从大到小枚举$k$，记录对应的$p[k]<p[i]$的最大值$mx$，如果$mx<p[j]<p[i]$则可以转移。

如果用线段树位置对应序列下标来维护转移，需要满足两个条件，并不好做。我们改为用线段树位置对应$p$，线段树节点的值对应序列下标，那么区间$[1,p[i]-1]$中值为后缀最大值的点即可作为转移点（p>这个点，则下标一定比这个点小）

好题。

Code：

#include<bits/stdc++.h> #define maxn 200005 using namespace std; const int inf = 2e9+1; int n,p[maxn],c[maxn],mx[maxn<<2],val[maxn<<2],vl[maxn<<2]; int calc(int i,int l,int r,int d){ if(l==r) return mx[i]>d?val[i]:inf; int mid=(l+r)>>1; if(mx[i<<1|1]<=d) return calc(i<<1,l,mid,d); else return min(vl[i],calc(i<<1|1,mid+1,r,d)); } void insert(int i,int l,int r,int p,int id,int v){ if(l==r) {mx[i]=id,val[i]=v;return;} int mid=(l+r)>>1; if(p<=mid) insert(i<<1,l,mid,p,id,v); else insert(i<<1|1,mid+1,r,p,id,v); mx[i]=max(mx[i<<1],mx[i<<1|1]),vl[i]=calc(i<<1,l,mid,mx[i<<1|1]); } int id,v; void query(int i,int l,int r,int p){ if(r<=p) {v=min(v,calc(i,l,r,id)),id=max(id,mx[i]);return;} int mid=(l+r)>>1; if(mid<p) query(i<<1|1,mid+1,r,p); query(i<<1,l,mid,p); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i]); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n*4;i++) vl[i]=inf; for(int i=1;i<=n;i++){ id=0,v=inf,query(1,1,n,p[i]); insert(1,1,n,p[i],i,(v<inf?v:0)+c[i]); } id=0,v=inf,query(1,1,n,n); printf("%d\n",v); }

---

T3：Lost My Music

把$\frac{c_v-c_u}{de{p}_u-de{p}_v}$乘以-1就变成了斜率的形式，求原数的最小值即求斜率的最大值，于是问题变成了维护祖先的凸包，又因为dep单增，所以想维护祖先的单调栈。 dfs时暴力弹栈可能被卡成O(n²)，我们需要可持久化栈。

因为当前点与凸包上的点的斜率是有单调性的，所以我们可以二分凸包上的祖先，栈都可以不用存，直接用倍增数组实现，点这里有更详细的解析。

Code：

#include<bits/stdc++.h> #define maxn 500005 using namespace std; char cb[1<<18],*cs,*ct; #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<18,stdin),cs==ct)?0:*cs++) inline void read(int &a){ char c;while(!isdigit(c=getc())); for(a=c-'0';isdigit(c=getc());a=a*10+c-'0'); } const int Log = 18; int n,c[maxn],dep[maxn],fa[maxn],f[maxn][Log+1]; int fir[maxn],nxt[maxn],to[maxn],tot; inline void line(int x,int y){nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y;} inline bool check(int k,int j,int i){return 1ll*(c[i]-c[k])*(dep[i]-dep[j])>=1ll*(c[i]-c[j])*(dep[i]-dep[k]);} void dfs(int u){ dep[u]=dep[fa[u]]+1; int x=fa[u],t; for(int i=Log;i>=0;i--){//二分凸包祖先 if((t=f[x][i])<2) continue; if(check(f[t][0],t,u)) x=t; } if(x!=1&&check(f[x][0],x,u)) x=f[x][0]; f[u][0]=x; for(int i=1;i<=Log;i++) f[u][i]=f[f[u][i-1]][i-1]; for(int i=fir[u];i;i=nxt[i]) dfs(to[i]); } int main() { read(n); for(int i=1;i<=n;i++) read(c[i]); for(int i=2;i<=n;i++) read(fa[i]),line(fa[i],i); dfs(1); for(int i=2;i<=n;i++) printf("%.10f\n",(c[f[i][0]]-c[i])*1./(dep[i]-dep[f[i][0]])); //最优的点就是凸包上的前一个点 }

鉴于这道题只需要求一个答案，并不需要保存倍增数组，我们可以在dfs时将凸包存入栈中，然后二分当前点应该插入到栈的哪个位置，直接令那个位置=当前点，然后递归儿子，因为只改动了一个点，所以存下那个位置原来的数，退出dfs时将其还原即可。 其实就是利用凸包的单调性将暴力弹栈改为二分弹栈位置。