题目描述
小$w$来到天堂的门口，对着天堂的大门发呆。
大门上有一个二分图，左边第$i$个点连到右边第$p_i$个点。（保证$p_i$是一个排列）。
小$w$每次可以找左边某个对应连线尚未被移除的点$i$，付出$c_i$的代价之后删除左边第$i$个点到右边第$p_i$个点的连线，以及所有和它们相交的连线。
请问小$w$最少要花多少钱来删除所有连线？
输入格式
一行一个整数$n$表示两边点的个数。
一行$n$个整数表示$p_i$。
一行$n$个整数表示$c_i$。
输出格式
一行一个整数表示答案。
样例
样例输入：
5
3 1 4 5 2
3 4 3 4 1
样例输出：
5
数据范围与提示
对于$20\%$的数据，$nleqslant 10$。
对于$40\%$的数据，$nleqslant 1,000$。
对于另外$20\%$的数据，$|i-p_i|leqslant 5$。
对于$100\%$的数据，$nleqslant 2 imes {10}^5,c_ileqslant 10,000$。
题解
认真思考一下问题，其实我们就是要求一个极长上升序列。
设$dp[i]$表示左边最后一个选的谁的最大贡献。
每次转移的时候枚举一个前面既不相交，又能保证极长的$j$转移。
然而这样做的时间复杂度显然是$Theta(n^2)$的。
因为$j$满足单调性，其一定是一个上升序列，那么我们可以用线段树来维护这个上升序列。
时间复杂度：$Theta(nlog^2n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int n;
int p[200001],c[200001];
int trmax[1000000],trmin[1000000];
int res,dp[200001];
void askmax(int x,int l,int r,int L,int R)
{
if(r<L||R<l)return;
if(L<=l&&r<=R)
{
res=max(res,trmax[x]);
return;
}
int mid=(l+r)>>1;
askmax(L(x),l,mid,L,R);
askmax(R(x),mid+1,r,L,R);
}
int ask(int x,int l,int r,int w)
{
if(w>trmax[x])return 1<<30;
if(l==r)return dp[trmax[x]];
int mid=(l+r)>>1;
if(w>trmax[R(x)])return ask(L(x),l,mid,w);
return min(trmin[x],ask(R(x),mid+1,r,w));
}
void pushup(int x,int l,int r)
{
trmax[x]=max(trmax[L(x)],trmax[R(x)]);
int mid=(l+r)>>1;
if(trmax[R(x)]==-1044266559)trmin[x]=ask(L(x),l,mid,0);
else trmin[x]=ask(L(x),l,mid,trmax[R(x)]);
}
void change(int x,int l,int r,int d,int w)
{
if(l==r)
{
trmax[x]=w;
return;
}
int mid=(l+r)>>1;
if(d<=mid)change(L(x),l,mid,d,w);
else change(R(x),mid+1,r,d,w);
pushup(x,l,r);
}
int askmin(int x,int l,int r,int R)
{
if(R<l)return 1<<30;
if(r<=R)
{
if(r+1<=R)
{
res=-1;
askmax(1,1,n,r+1,R);
return ask(x,l,r,res);
}
return ask(x,l,r,0);
}
int mid=(l+r)>>1;
return min(askmin(L(x),l,mid,R),askmin(R(x),mid+1,r,R));
}
int main()
{
memset(trmax,-0x3f,sizeof(trmax));
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]);
change(1,0,n,0,0);
for(int i=1;i<=n;i++)
{
dp[i]=askmin(1,0,n,p[i])+c[i];
change(1,0,n,p[i],i);
}
cout<<askmin(1,0,n,n);
return 0;
}
rp++