ABC275F Monster
其实就是对凸壳的处理办法
显然建立 \(B\) 的笛卡尔树，设 \(f[i,j]\) 为树 \(i\) 操作后最大值 \(\le j\) 的最小代价。
显然离开子树后子树都是整体操作的
有
\[f[i,j]=\min(f[i,j-1],f[lc,x]+f[rc,y]+\max(\max(x,y)-j,0)\times B_i)\\ \]显然可以优化为：
\[\begin{aligned} j:&\max\to 0,f'[i,j]=\min(f'[i,j+1]+B[i],f[lc,j]+f[rc,j])\\ j:&0\to \max,f'[i,j]=\min(f'[i,j-1],f'[i,j]) \end{aligned} \]现在我们做到了 \(O(nv)\)，显然 \(v\) 可以离散化得到 \(O(n^2)\)
换个写法：
\[f[i,j]=\min_{k=0}^{\max(A_i-j,0)}(f[lc,j+k]+f[rc,j+k]+kB_i) \]\(siz_i=1\) 时是一条直线
当合并时这个形式感觉由于 \(B\) 递增会有斜率递增的凸性
容易发现由于 \(f\) 的递减，\(siz_i=1\) 的时候有凸性，大胆猜测整个函数有凸性。
首先假定成立，则设 \(s(x)=f_{lc}(x)+f_{rc}(x)\) 有凸性且递减，则比较决策对于 \(j\)，\(k ,k+1\),有：
\(s(k)+kB_i-s(k+1)+(k+1)B_i=s(k)-s(k+1)-B_i\)
相当于把 \((k,s(k))\to (k+1,s(k+1))\) 之间的斜率与 \(B\) 取较小值。
那么在原本的斜率递增的情况下会删除一个尾巴/脑袋，还是递增的。
而且至多有 \(siz\) 段不同的斜率，每段最多删一次。
考虑用数据结构维护斜率，然后每次删除增加，我们需要启发式合并？。
不妨维护 \((pos,\Delta y)\)（\(\Delta x=1\)），用可并堆（\(pos_{\min}\) 的左偏树就行）
讲讲实现（谁再喷我水）：
维护 \(f0_i\) 表示树 \(i\) 凸包的首项，也就是上面的 \(f_{i,0}\)。
然后维护 \((pos,\Delta y)\)，比如一棵树初始化是 \((0,b_i),(a_i,0)\)，和其两个子树的凸包合起来。插入 \((0,b_i)\) 这是因为实现方程里面的 \(f[i,j]=\min_{k=0}^{\max(A_i-j,0)}(f[lc,j+k]+f[rc,j+k]+(j+k)B_i)-jB_i\)。\(j+k\) 这一项，而 \((a_i,0)\) 是卡住上界。
（可以看作是三个凸包，\(f[lc],f[rc]\) 以及 \(0,B_i,2B_i……\) 的和）
然后我们将斜率小于零的部分以及初始位置小于 \(a_i\) 的部分全部删去（因为你必须要操作根节点）。注意删完了要加一个新的首项进去。
接着我们插入 \((0,-b_i)\) ，这是因为实现方程里面的 \(f[i,j]=\min_{k=0}^{\max(A_i-j,0)}(f[lc,j+k]+f[rc,j+k]+(j+k)B_i)-jB_i\)。
注意到我们只需要维护这些二元组的快速合并和查首项，用可并堆（左偏树）即可。
#include<bits/stdc++.h>
using namespace std;
#define N 105050
#define int long long
namespace heap{
int cnt,lc[N<<2],rc[N<<2],dep[N<<2],px[N<<2],dk[N<<2];
int new_node(int x,int k){
px[++cnt]=x;dk[cnt]=k;return cnt;
}
int merge(int a,int b){
/*
维护一个px的左偏树小根堆方便删
*/
if(!a||!b)return a^b;
if(px[a]>px[b]||(px[a]==px[b]&&dk[a]>dk[b]))swap(a,b);
rc[a]=merge(rc[a],b);
if(dep[lc[a]]<dep[rc[a]])swap(lc[a],lc[b]);
dep[a]=dep[rc[a]]+1;return a;
}
}
int lc[N],rc[N],a[N],b[N],sta[N],top,rt[N],f0[N],n,m;
void sol(int x){
if(!x)return ;
sol(lc[x]);sol(rc[x]);
f0[x]=f0[lc[x]]+f0[rc[x]];
rt[x]=heap::merge(rt[lc[x]],heap::merge(rt[rc[x]],heap::new_node(0,b[x])));
//f[x,i]=min_{j>=i}(f[lc,j]+f[rc,j]+(j-i)*b[x])=min(f[lc,j]+f[rc,j]+j*b[x])-b[x]*i
/*
初始化这棵树是(a[x],0) & (0,b[x])
也即f[x,a[x]]之后的全0，前面的每个增量是b[x]
*/
int k=0;
while(k+heap::dk[rt[x]]<0||heap::px[rt[x]]<a[x]){
k+=heap::dk[rt[x]];int tmp=heap::px[rt[x]];
rt[x]=heap::merge(heap::lc[rt[x]],heap::rc[rt[x]]);
f0[x]+=(heap::px[rt[x]]-tmp)*k;
}
rt[x]=heap::merge(rt[x],heap::merge(heap::new_node(heap::px[rt[x]],k),heap::new_node(0,-b[x])));
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)cin>>b[i];
int rot=0;
for(int i=1;i<=n;i++){
int k=top;
while(k&&b[sta[k]]<b[i])--k;
if(k)rc[sta[k]]=i;
if(k<top)lc[i]=sta[k+1];
sta[++k]=i,top=k;
}
int mx=-0x3f3f3f3f,id=n;
for(int i=1;i<=n;i++)if(b[i]>mx)mx=b[i],id=i;
sol(id);
cout<<f0[id]<<"\n";
}
APIO2016 划艇
题意就是给定若干 \([l_i,r_i]\)，保证正整数。
要求对于其所有子序列而言，子序列每个数只能出现 \([l_i,r_i]\)，定义一个子序列的权值是其最长的上升子序列个数，求所有子序列权值之和。
显然有一个 \(dp\) 是设 \(f_{i,j}\) 为位置 \(i\) 选了，且用的是 \(j\) 的方案数，有：
\[f_{i,j}=\sum _{k<i,p<j}f_{k,p} \]一个有点像二维前缀和的东西。
可以修改定义为 \([1,i]\) 最后一个位置是 \(j\) 的方案数，有：
\[f_{i,j}=f_{i-1,j}+\sum_{p<j}f_{i-1,p} \]注意到第二维很大，有 \(O(V)\)，能不能考虑将 \(1\sim V\) 依次填入序列，但这是徒劳的。
感觉最开始那个二位前缀和还有优化空间，不妨设 \(S\)，那就有：
\[S_{i,j}-S_{i-1,j}-S_{i,j-1}+S_{i-1,j-1}=S_{i-1,j-1}\implies S_{i,j}=S_{i-1,j}+S_{i,j-1} \]这是 \(j\in [l_i,r_i]\)，若 \(j\notin [l_i,r_i]\) 则？
还是很那个。我们的核心问题在于减少第二维的状态。
考虑修改状态为：将 \(l,r\) 离散化后形成若干区间，设 \(f_{i,j,k}\) 为第 \(i\) 个位置落在第 \(j\) 个区间的第 \(k\) 个位置的方案数。
诚然这很难以转移，但是我们不妨一整个转移，略去 \(k\)，\(f_{i,j}=\sum_{p<j} f_{k,p}·(\sum_{x=0}^{c[k+1,i-1]}{len\choose x+1}{c[k+1,i-1]-1\choose x})\)，也就是这个区间内所有在这个区间里的数字选与不选，强行钦定 \(i\) 必须要选？其实感觉不需要。
我们对第二维做一个前缀和好像就做完了。
对于转移系数可以 \(O(n^3)\) 预处理。
\(O(n^3)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
#define N 1505
int b[N],f[N][N<<1],s[N][N<<1],trans[N][N<<1],n,m,l[N],r[N],cnt[N][N<<1],zhs[N<<1][N],jc[N],inv[N];
int power(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;
}
return ans;
}
int C(int n,int m){
if(n<m)return 0;
if(n-m<m)m=n-m;int res=1;
for(int i=n;i>n-m;--i)res=res*i%p;
res=res*inv[m]%p;return res;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;jc[0]=1;
for(int i=1;i<=n;++i)jc[i]=jc[i-1]*i%p;inv[n]=power(jc[n],p-2);
for(int i=n;i;--i)inv[i-1]=inv[i]*i%p;
for(int i=1;i<=n;++i)cin>>l[i]>>r[i],b[++m]=l[i],++r[i],b[++m]=r[i];
sort(b+1,b+m+1);m=unique(b+1,b+m+1)-b-1;
f[0][0]=s[0][0]=1;
for(int i=1;i<=m;++i)s[0][i]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<m;++j)cnt[i][j]=cnt[i-1][j];
for(int j=1;j<m;++j)if(l[i]<=b[j]&&b[j+1]<=r[i])cnt[i][j]++;
}
for(int j=1;j<m;++j){
for(int i=0;i<=cnt[n][j];++i){
zhs[j][i]=C(b[j+1]-b[j],i);
}
for(int i=1;i<=cnt[n][j];++i){
for(int x=0;x<i;++x)(trans[i][j]+=zhs[j][x+1]*jc[i-1]%p*inv[x]%p*inv[i-1-x]%p)%=p;
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<m;++j){
if(l[i]<=b[j]&&b[j+1]<=r[i]){
for(int k=0;k<i;++k){
int len=b[j+1]-b[j],c=cnt[i][j]-cnt[k][j];
f[i][j]+=s[k][j-1]*trans[c][j]%p;
}
}
f[i][j]%=p;
s[i][j]=(f[i][j]+s[i][j-1])%p;
}
}
int res=0;res=(res%p+p)%p;
for(int i=1;i<=n;++i)res=(res+s[i][m-1])%p;
res=(res%p+p)%p;
cout<<res<<"\n";
}
/*
3
1 5 3 9 2 7
*/
Apio2016 烟火表演
弄出monster之后这题我谔谔
容易写出朴素DP式，也就是 \(f_{i,j}\) 表示子树 \(i\) 所有叶子到 \(i\) 距离为 \(j\) 的最小代价，有：
\(f'_{i,j}=\min_{k\le j} f_{i,j}+f_{son,k}+|w(i,son)-(j-k)|\)
发现绝对值函数是凸的，所以叶子的 \(f\) 是凸的，进而这相当于是三个凸包的 \((\min,+)\) 卷积，所以 \(f'\) 是凸的，也即我们归纳证明了 \(f\) 是凸的。由于绝对值函数是下凸的，所以 \(f\) 是下凸的。
然后我们考虑一个绝对值函数有什么影响。
由于我们关心最小值，所以我们只关心斜率为 \(0\) 的段，先看看这一段如何变化。
不难发现假设原本段是 \([l,r]\)，变化后等价于 \(\le l\) 的部分向上平移 \(w\)，\([l,r]\) 向右平移 \(w\)，而新的 \([l,l+w]\) 斜率成了负一，后面的斜率全部改成 \(1\)。
我们只关心最小值，所以我们只需要维护半个凸壳，也就是 \(k\le 0\) 的部分。
那么我们可以忽略 \(k>0\) 的变化，现在问题变成了如何在合并儿子后删掉后面。
其实是简单的，有 \(c\) 个儿子就会有 \(c-1\) 个斜率正的段，直接删掉即可（增加了 \(c-1\) 个拐点）。
（我们并没有管它，但是它合并上来后会形成拐点）
发现我们只需要维护凸壳上点的横坐标，维护即可。
也即使用一个可并堆（大根堆删后面），依次合并儿子，然后弹出前面的 \(c-1\) 个，并再弹出两个作为 \([l,r]\) 整体平移后又插回去，注意到点变化后自然会继承前面的负斜率导致前面一截斜率是 \(-1\)。
这里注意对于叶子节点而言，即使这是一个点也要看成一段，这是 \(c-1\) 个的依据（段段合并）。
#include<bits/stdc++.h>
using namespace std;
#define N 656500
#define int long long
int lc[N<<1],rc[N<<1],x[N<<1],d[N<<1],cnt;
namespace heap{
int new_node(int v){
++cnt;x[cnt]=v;return cnt;
}
int merge(int a,int b){
if(!a||!b)return a^b;
if(x[a]<x[b])swap(a,b);
rc[a]=merge(rc[a],b);
if(d[lc[a]]<d[rc[a]])swap(lc[a],rc[a]);
d[a]=d[rc[a]]+1;
return a;
}
}
vector<int>e[N];
int rt[N],dis[N],n,m,ans,fa[N];
void dfs(int u){
if(u>n){rt[u]=heap::merge(heap::new_node(dis[u]),heap::new_node(dis[u]));return ;}
for(auto v:e[u]){
dfs(v);rt[u]=heap::merge(rt[u],rt[v]);
}
for(int i=e[u].size()-1;i;--i)rt[u]=heap::merge(lc[rt[u]],rc[rt[u]]);
if(u==1){
rt[u]=heap::merge(lc[rt[u]],rc[rt[u]]);
while(rt[u])ans-=x[rt[u]],rt[u]=heap::merge(lc[rt[u]],rc[rt[u]]);return ;
}
int posr=x[rt[u]];rt[u]=heap::merge(lc[rt[u]],rc[rt[u]]);
int posl=x[rt[u]];rt[u]=heap::merge(lc[rt[u]],rc[rt[u]]);
rt[u]=heap::merge(rt[u],heap::merge(heap::new_node(posl+dis[u]),heap::new_node(posr+dis[u])));
}
signed main(){
cin>>n>>m;
for(int i=2,f;i<=n+m;++i)cin>>f>>dis[i],e[f].push_back(i),ans+=dis[i],fa[i]=f;
dfs(1);
cout<<ans<<"\n";
}