链接

　　http://www.lydsy.com/JudgeOnline/problem.php?id=3173

题解

　　我跟你讲啊，这题我死磕了一下午，就是想不出来怎么构造最后的那个序列。 　　还是看题解比较爽。 　　开个 BIT ，每个位置加一，表示所有位置都放上数了。 　　然后我们倒着搞，如果一个数你读入的是 pos ，那我就找前 pos 个 1 ，最后一个1所在的位置就是我这个数最终的位置，搞完这个数之后把它最终位置上的那个 1 删掉。 　　考虑下这个算法的正确性，搞一个数的时候，它后面的那些数的正确位置上都是0，那么这个数面临的就是第一个数到这个数的位置上都是 1 的情况，你又知道它是第pos个，所以就是这样啦。 　　然后最后的求答案我比较傻用的 CDQ 分治，看了题解发现其实只要普通求 LIS 就行了… 　　时间复杂度是 O(nlogn) 。 　　 BIT 前 k <script type="math/tex" id="MathJax-Element-1001">k</script>大有神奇的技巧，具体看程序

代码

//平衡树 + CDQ分治 + 树状数组 #include <cstdio> #include <algorithm> #define maxn 100010 #define lowbit(x) (x&-x) using namespace std; int bit[maxn], N, final[maxn], mini[maxn], ndtot; struct number{int pos, w, f;}num[maxn]; inline int read(int x=0) { char c=getchar(); while(c<48 or c>57)c=getchar(); while(c>=48 and c<=57)x=(x<<1)+(x<<3)+c-48, c=getchar(); return x; } inline bool operator<(number a, number b){return a.w<b.w;} void bitadd(int pos, int v) {for(;pos<=N;pos+=lowbit(pos))bit[pos]+=v;} void bitins(int pos, int v) {for(;pos<=N;pos+=lowbit(pos))bit[pos]=max(bit[pos],v);} int bitmax(int pos) {int ans=0;for(;pos;pos-=lowbit(pos))ans=max(ans,bit[pos]);return ans;} void biterase(int pos) {for(;pos<=N;pos+=lowbit(pos))bit[pos]=0;} int bitkth(int k) { int res=0, cnt=0, i; for(i=17;~i;i--) { res+=1<<i; if(res>N or cnt+bit[res]>=k)res-=1<<i; else cnt+=bit[res]; } return res+1; } void init() { int i, j, t; N=read(); for(i=1;i<=N;i++)num[i].w=i, num[i].pos=read()+1; for(i=1;i<=N;i++)bitadd(i,1); for(i=N;i>=1;i--) { t=bitkth(num[i].pos); bitadd(t,-1); num[i].pos=t; } } void cdq(int l, int r) { int mid=l+r>>1, i, j; if(l==r)return; cdq(l,mid); for(i=l;i<=mid;i++)bitins(num[i].pos,num[i].f); for(i=mid+1;i<=r;i++)num[i].f=max(num[i].f,bitmax(num[i].pos)+1); for(i=l;i<=mid;i++)biterase(num[i].pos); cdq(mid+1,r); } int main() { int ans=0; init(); for(int i=1;i<=N;i++)num[i].f=1; cdq(1,N); for(int i=1;i<=N;i++) { ans=max(ans,num[i].f); printf("%d\n",ans); } return 0; }