首页 > 代码库 > bzoj3173 [Tjoi2013]最长上升子序列

bzoj3173 [Tjoi2013]最长上升子序列

2024-11-23 15:00:02   203人阅读

Description

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

Input

第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

Output

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

Sample Input

3
0 0 2

Sample Output

1
1
2

HINT

 

X0等于0 ，我们将1插入到位置0得到序列{1}

X1等于0 ，我们将1插入到位置0得到序列{2，1}

X2等于2 ，我们将1插入到位置0得到序列{2，1，3}



数据范围

30%?的数据 n<=1000

100%的数据 n<=100000

 
这题……看上去不难……但是为什么我wa的停不下来
首先先随便搞搞把最终得到的数列求出来。treap和splay都行。spaly也没话说
有一点很重要！左旋右旋更新儿子信息的时候一定要先更新k再更新t，因为旋完t是在k上面的（啊啊啊啊啊啊就是这里我跪的停不下来了）
然后就可以考虑怎样计算lis了
其实一开始在这里我有点乱了。显然我们只要求1到i中小于等于a[i]的数字的lis就好了
先随便画几组数据
7
0 0 1 3 2 4 2
算出来数列是 2 3 7 5 1 6 4
那么以4为例，有用的是2 3 1 4子序列。要在子序列上跑lis
可以这样做：求出一定包含a[i]的lis，然后搞出前缀和，就是包含1、2、3、4的lis啦
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7fffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}struct treap{int l,r,rnd,son;}tree[100010];int n,len,mx,root,treesize;int a[100010],mn[100010],ans[100010],f[100010],rnk[100010];inline void update(int k){    tree[k].son=tree[tree[k].l].son+tree[tree[k].r].son+1;}inline void right_rotate(int &k){    int t=tree[k].l;    tree[k].l=tree[t].r;    tree[t].r=k;    update(k);    update(t);    k=t;}inline void left_rotate(int &k){    int t=tree[k].r;    tree[k].r=tree[t].l;    tree[t].l=k;    update(k);    update(t);    k=t;}inline void insert(int &k,int rnk){    if (!k)    {        k=++treesize;        tree[k].rnd=rand();        tree[k].son=1;        return;    }    tree[k].son++;    if (tree[tree[k].l].son<rnk)    {        insert(tree[k].r,rnk-tree[tree[k].l].son-1);        if (tree[tree[k].r].rnd>tree[k].rnd)left_rotate(k);    }else    {        insert(tree[k].l,rnk);        if (tree[tree[k].l].rnd>tree[k].rnd)right_rotate(k);    }}inline void dfs(int x){    if (!x)return;    dfs(tree[x].l);a[++len]=x;dfs(tree[x].r);}inline int bsearch(int x){    int l=1,r=mx,s=0;    while (l<=r)    {        int mid=(l+r)>>1;        if(mn[mid]<x){s=mid;l=mid+1;}        else r=mid-1;    }    return s;}int main(){    srand(1);    n=read();    for (int i=1;i<=n;i++)    {        int x=read();        insert(root,x);    }    dfs(root);    mx=1;mn[1]=a[1];ans[a[1]]=1;    for (int i=2;i<=n;i++)     {        int find=bsearch(a[i]);        if (find==mx)mn[++mx]=a[i];          else if (mn[find+1]>a[i])mn[find+1]=a[i];          ans[a[i]]=find+1;     }      for (int i=2;i<=n;i++)ans[i]=max(ans[i],ans[i-1]);    for (int i=1;i<=n;i++)        printf("%d\n",ans[i]);}

 

bzoj3173 [Tjoi2013]最长上升子序列


联系
我们