给出1~n的插入顺序，要求每次插入之后的LIS
对于样例：
0:1插入到当前第0个位置后 1
0:2插入到当前第0个位置后 2 1
2:3插入到当前第2个位置后 2 1 3
线段树处理空格填数问题，然后做LIS
难点主要是如何处理LIS，，因为每次填入的数字都是递增的，所以1——>n循环下去一定是递增的。
mark记录每个数字的位置，因为数值递增，所以在保证LIS足够长的情况下，位置小的取小者，最后可以得到最长的值
#include "stdio.h"#include "string.h"#include "algorithm"using namespace std;struct Data{int l,r,x;}data[400010];int dp[100010],mark[100010],a[100010],cnt;void build(int l,int r,int k){int mid;data[k].l=l;data[k].r=r;data[k].x=r-l+1;if (l==r) return ;mid=(l+r)/2;build(l,mid,k*2);build(mid+1,r,k*2+1);}void updata(int x,int op,int k){if (data[k].l==data[k].r){data[k].x=0;mark[op]=data[k].l;return ;}data[k].x–;if (data[k*2].x>=x) updata(x,op,k*2);else updata(x-data[k*2].x,op,k*2+1);}int two_search(int x){int l,r,mid;l=1; r=cnt;while (l<=r){mid=(l+r)/2;if (dp[mid]<x) l=mid+1;else r=mid-1;}return l;}int Max(int a,int b){if (a<b) return b;else return a;}int main(){int T,Case,i,n,temp;scanf("%d",&T);Case=1;while (T–){scanf("%d",&n);for (i=1;i<=n;i++)scanf("%d",&a[i]);printf("Case #%d:\n",Case++);build(1,n,1);for (i=n;i>=1;i–)updata(a[i]+1,i,1);memset(dp,0,sizeof(dp));cnt=0;for (i=1;i<=n;i++){temp=two_search(mark[i]);cnt=Max(cnt,temp);dp[temp]=mark[i];printf("%d\n",cnt);}printf("\n");}return 0;}
我想，这就是旅行的真义吧。
