bzoj3173 [Tjoi2013]最长上升子序列-白红宇

bzoj3173 [Tjoi2013]最长上升子序列

阅读量：5052 次

发布时间：2019-06-12

本文共 2275 字，大约阅读时间需要 7 分钟。

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

0 0 2

Sample Output

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就好了

先随便画几组数据

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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #define LL long long#define inf 0x7fffffff#define pa pair
                 
                  #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
                  
                   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]
                   
                    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]);}

转载于:https://www.cnblogs.com/zhber/p/4263431.html

你可能感兴趣的文章