hdu6635 Nonsense Time 2019杭电多校第六场

hdu6635 Nonsense Time 2019杭电多校第六场

随机数据期望是sqrt(n)的最长上升子序列。。。

所以用倒着来做，每次删除数字，如果删除的在当前的最长上升子序列中就重新找一个最长上升子序列

期望只要重构sqrt (n)次，那么复杂度为O(nsqrt(n)logn)

线段树被卡常，树状数组5600ms过了

#include<bits/stdc++.h>
#define maxl 50010
using namespace std;int n,mxid,mxval;
int a[maxl],kk[maxl],dy[maxl],ans[maxl];
int b[maxl],dp[maxl],frm[maxl];
bool in[maxl],froz[maxl];inline void prework()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),dy[a[i]]=i;for(int i=1;i<=n;i++)scanf("%d",&kk[i]),froz[i]=false;
}inline void upd(int i,int x)
{while(i<=n){if(dp[b[i]]<dp[x])b[i]=x;i+=i&-i;}
}inline int qry(int i)
{int res=0;while(i){if(dp[res]<dp[b[i]])res=b[i];i-=i&-i;}return res;
}inline void lis()
{for(int i=1;i<=n;i++)in[i]=false,frm[i]=0,b[i]=0,dp[i]=0;int id;mxval=0;mxid=0;for(int i=1;i<=n;i++)if(!froz[i]){id=qry(a[i]);dp[i]=dp[id]+1;frm[i]=id;if(dp[i]>mxval)mxval=dp[i],mxid=i;upd(a[i],i);}int u=mxid;while(u!=0)in[u]=true,u=frm[u];
}inline void mainwork()
{lis();for(int i=n;i>=1;i--){ans[i]=mxval;froz[kk[i]]=true;if(in[kk[i]])lis();}
}inline void print()
{for(int i=1;i<=n;i++)printf("%d%c",ans[i],(i==n)?'n':' ');
}int main()
{int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0;
}