A. Star Way To Heaven

如果二分答案，问题就转化为不经过一些等大的圆，能否从左侧到达右侧。

然后我就不会了。

其实问题很简单：

不能从左侧走到右侧，等价于能从下侧沿障碍走到上侧，也就是说一些圆将路阻断开。

二分答案，用并查集或者dfs都可以做到$O(k^2)$建边之后$O(k)$（不计并查集）验证。

总复杂度$O(k^2logn)$。

其实问题就是一个最小瓶颈生成树，prim $O(k^2)$求解。

 

 

 

B. God Knows

感觉是dp，然而打不出来，只会打搜索。

只有颓题解才能维持生活这样子：

设$dp[i]$表示i以前的点引出的边已经切掉了，选了第i个点引出的边。

$dp[i]=\min \limits_{j<i,p[j]<p[i],\forall k,j<k<i,p[k]<p[j]或p[k]>p[i]}dp[j]+c[i]$

转化一下，即

设$mx[j][i]=\max \limits_{j<k<i,p[k]<p[i]}p[k]$

则$dp[i]=\min \limits_{j<i,mx[j][i]<p[j]<p[i]}dp[j]+c[i]$

$mx$的变化可以继承已有信息，于是得到了$O(n^2)$的算法。

注意：以上纯属意淫出了一个根本无法导向正解的死掉的思路。

下面是将以上思路转化后的结果：

根据以上的式子，发现能更新dp[i]的，

为$dp[j]$，并且要保证j为j～i中p值小于$p[i]$中最大的。

即，能更新i的是1~i中小于$p[i]$的一段p值单调递减的子序列，要维护的是这段子序列里的dp最小值。

但是因为受小于$p[i]$限制，难以维护。

于是接着转换思路，

因为i与$p[i]$一一对应，将坐标系翻转，于是不再受p[i]限制。

p[i]随i单调递减，变为i随p[i]单调递减。

然而仍然无法维护，询问的p[i]是跳跃的。

线段树维护区间的单调栈，与某个名叫Weed的题异曲同工，

维护了栈内最小值，左儿子被右儿子更新之后的最小值，右儿子栈底的元素。

维护时每次延伸出一条链查找答案。

询问时先找右侧，以得到栈的下一个元素，确定这一次的询问范围。

注意一些细节就可以了。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define lch (p<<1)
 5 #define rch (p<<1|1)
 6 using namespace std;
 7 const int N=2e5+10;
 8 const int inf=2e9;
 9 int n;
10 int to[N],w[N];
11 inline int read(register int x=0,register char ch=getchar(),bool ff=0){
12     while(!isdigit(ch)) ff=(ch=='-'),ch=getchar();
13     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
14     return ff?-x:x;
15 }
16 struct node{
17     int l,r,mn,mx,upd_mn;
18 }s[N<<2];
19 void build(int p,int l,int r){
20     s[p].l=l; s[p].r=r;
21     s[p].mn=s[p].upd_mn=inf;
22     s[p].mx=-1;
23     if(l==r) return ;
24     int mid=l+r>>1;
25     build(lch,l,mid);
26     build(rch,mid+1,r);
27 }
28 int calc(int p,int nxt){
29     if(s[p].l==s[p].r) return s[p].mx>nxt?s[p].mn:inf;
30     if(s[rch].mx>nxt) return min(s[lch].upd_mn,calc(rch,nxt));
31     return calc(lch,nxt);
32 }
33 int nxt;
34 int query(int p,int l,int r){
35     if(s[p].l>=l&&s[p].r<=r){
36         int ans=calc(p,nxt);
37         nxt=max(s[p].mx,nxt);
38         return ans;
39     }
40     int ans=inf;
41     if(r>=s[rch].l) ans=min(query(rch,l,r),ans);
42     if(l<=s[lch].r) ans=min(query(lch,l,r),ans);
43     return ans;
44 }
45 void insert(int p,int pos,int tail,int val){
46     if(s[p].l==s[p].r){
47         s[p].mn=val;
48         s[p].mx=tail;
49         return ;
50     }
51     if(pos<=s[lch].r) insert(lch,pos,tail,val);
52     else insert(rch,pos,tail,val);
53     s[p].mx=max(s[lch].mx,s[rch].mx);
54     s[p].mn=min(s[rch].mn,s[lch].upd_mn=calc(lch,s[rch].mx));
55 }
56 int main(){
57     n=read();
58     for(int i=1;i<=n;++i) to[i]=read();
59     for(int i=1;i<=n;++i) w[i]=read();
60     ++n; to[n]=n; build(1,0,n);
61     insert(1,0,0,0);
62     for(int i=1,k;i<=n;++i){
63         nxt=-1; k=query(1,0,to[i]-1)+w[i];
64         insert(1,to[i],i,k);
65         if(i==n) printf("%d\n",k);
66     }
67     return 0;
68 }
View Code

 

 

 

 

C. Lost My Music

考场上切掉的简单题。

然而我的复杂度比正解多一个$log$。

观察到给出的式子正是斜率的负值，

于是问题转化为求祖先链上的最大斜率，并将答案设为它的相反数。

显然用栈维护下凸包即可。

然而需要考虑的是对于一个节点不止一个儿子，一些信息该怎样继承。

我用了树上启发式合并的思想，直接更新轻儿子，让重儿子继承栈内的信息，最后将栈清空，走轻儿子。

单次更新的复杂度为$O(logn)$，每个儿子最多被更新$logn$次，总复杂度为$O(nlog^2n)$。

正解是使用可持久化链栈，通过倍增弹栈，总复杂度为$O(nlogn)$。

注意如果暴力弹栈入栈，可能会被长链套菊花的数据卡为$O(n^2)$。