Bzoj 3173: [Tjoi2013]最长上升子序列 平衡树,Treap,二分,树的序遍历

时间:2022-12-25 13:23:54

3173: [Tjoi2013]最长上升子序列

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1183  Solved: 610
[Submit][Status][Discuss]

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

100%的数据 n<=100000

Source

 
题解:
Treap+中序遍历+二分。
先把所有数字加入,这用平衡树维护即可(但要记得加入的是位置)。
然后中序遍历搞出最终序列。
最后二分求最长上升子序列。(其实就是nlogn的求法)
 #include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
struct node
{
int left,right,val,size,count,rnd;
}tree[MAXN];
int ans[MAXN],v[MAXN],a[MAXN],SIZE,root,lv;
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void Update(int k){tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+;}
void Lturn(int &k){int t=tree[k].right;tree[k].right=tree[t].left;tree[t].left=k;tree[t].size=tree[k].size;Update(k);k=t;}
void Rturn(int &k){int t=tree[k].left;tree[k].left=tree[t].right;tree[t].right=k;tree[t].size=tree[k].size;Update(k);k=t;}
void Insert(int &k,int x)
{
if(k==)
{
SIZE++;k=SIZE;
tree[k].size=;tree[k].rnd=rand();
return;
}
tree[k].size++;
if(x<=tree[tree[k].left].size){Insert(tree[k].left,x);if(tree[tree[k].left].rnd<tree[k].rnd)Rturn(k);}
else {Insert(tree[k].right,x-tree[tree[k].left].size-);if(tree[tree[k].right].rnd<tree[k].rnd)Lturn(k);}
}
void dfs(int k)
{
if(k==)return;
dfs(tree[k].left);
v[++lv]=k;
dfs(tree[k].right);
}
int main()
{
int n,i,la,tmp,x;
n=read();
for(i=;i<=n;i++){x=read();Insert(root,x);}
lv=;
dfs(root);
memset(ans,,sizeof(ans));
la=;
for(i=;i<=n;i++)a[i]=INF;
for(i=;i<=n;i++)
{
tmp=upper_bound(a+,a+la+,v[i])-a;
a[tmp]=min(a[tmp],v[i]);
ans[v[i]]=tmp;
la=max(la,tmp);
}
for(i=;i<=n;i++)
{
ans[i]=max(ans[i-],ans[i]);
printf("%d\n",ans[i]);
}
return ;
}

Bzoj 3173: [Tjoi2013]最长上升子序列 平衡树,Treap,二分,树的序遍历的更多相关文章

  1. bzoj 3173 &lbrack;Tjoi2013&rsqb;最长上升子序列 (treap模拟&plus;lis)

    [Tjoi2013]最长上升子序列 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2213  Solved: 1119[Submit][Status] ...

  2. bzoj 3173&colon; &lbrack;Tjoi2013&rsqb;最长上升子序列【dp&plus;线段树】

    我也不知道为什么把题看成以插入点为结尾的最长生生子序列--还WA了好几次 先把这个序列最后的样子求出来,具体就是倒着做,用线段树维护点数,最开始所有点都是1,然后线段树上二分找到当前数的位置,把这个点 ...

  3. BZOJ 3173&colon; &lbrack;Tjoi2013&rsqb;最长上升子序列&lpar; BST &plus; LIS &rpar;

    因为是从1~n插入的, 慢插入的对之前的没有影响, 所以我们可以用平衡树维护, 弄出最后的序列然后跑LIS就OK了 O(nlogn) --------------------------------- ...

  4. BZOJ 3173&colon; &lbrack;Tjoi2013&rsqb;最长上升子序列

    3173: [Tjoi2013]最长上升子序列 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1524  Solved: 797[Submit][St ...

  5. BZOJ 3173&colon; &lbrack;Tjoi2013&rsqb;最长上升子序列 &lbrack;splay DP&rsqb;

    3173: [Tjoi2013]最长上升子序列 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1613  Solved: 839[Submit][St ...

  6. BZOJ 3173 &lbrack;Tjoi2013&rsqb; 最长上升子序列 解题报告

    这个题感觉比较简单,但却比较容易想残.. 我不会用树状数组求这个原排列,于是我只好用线段树...毕竟 Gromah 果弱马. 我们可以直接依次求出原排列的元素,每次找到最小并且最靠右的那个元素,假设这 ...

  7. BZOJ 3173&colon; &lbrack;Tjoi2013&rsqb;最长上升子序列 &lpar;线段树&plus;BIT&rpar;

    先用线段树预处理出每个数最终的位置.然后用BIT维护最长上升子序列就行了. 用线段树O(nlogn)O(nlogn)O(nlogn)预处理就直接倒着做,每次删去对应位置的数.具体看代码 CODE #i ...

  8. BZOJ 3173&colon; &lbrack;Tjoi2013&rsqb;最长上升子序列 Splay

    一眼切~ 重点是按照 $1$~$n$ 的顺序插入每一个数,这样的话就简单了. #include <cstdio> #include <algorithm> #define N ...

  9. bzoj3173&lbrack;Tjoi2013&rsqb;最长上升子序列 平衡树&plus;lis

    3173: [Tjoi2013]最长上升子序列 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2253  Solved: 1136[Submit][S ...

随机推荐

  1. 注解配置 ssh

    注解 <?xml version="1.0" encoding="UTF-8"? > <beans xmlns="http://ww ...

  2. ECMAScript中的两种属性

    数据属性 数据属性包含一个数据值的位置.在这个位置可以读取和写入值.数据属性一般用于存储数据数值. 数据属性有4个描述其行为的特征. configurable:true/false,是否可以通过del ...

  3. &lbrack;八&rsqb;基础数据类型之Double详解

    Double 基本数据类型double  的包装类 Double 类型的对象包含一个 double 类型的字段   属性简介 用来以二进制补码形式表示 double 值的比特位数 public sta ...

  4. image management in kubernet

    Image How can I edit an existing docker image metadata? docker-copyedit Registry Disk kubevirtis a g ...

  5. WMSYS&period;WM&lowbar;CONCAT返回CLOB类型的解决办法

    https://blog.csdn.net/cnm_csdn_wt/article/details/80047878

  6. Ansible5:常用模块

    目录 ping模块 setup模块 file模块 copy模块 service模块 cron模块 yum模块 user模块与group模块 user模块 group示例 synchronize模块 f ...

  7. Xcode6中手动添加Precompile Prefix Header

    Xcode5中创建一个工程的时候,系统会自动创建一个以以工程名为名字的pch(Precompile Prefix Header)文件,开发的过程中可以将广泛使用的头文件以及宏包含在该文件下,编译器就会 ...

  8. 实现全站 HTTPS &comma;为什么国内网站总是那么slow&amp&semi;&amp&semi;low呀!

    1 https://konklone.com/post/switch-to-https-now-for-free# https://theintercept.com/2014/11/20/non-pr ...

  9. log4j的简单使用

    引入jar包org.apache.log4j.Logger,项目src目录下建立一个log4j.properties配置文件 log4j.rootLogger=INFO,A1,R log4j.appe ...

  10. 关于 Delphi 中流的使用&lpar;1&rpar; 用 TMemoryStream&lpar;内存流&rpar; 入门 &amp&semi;&amp&semi;&amp&semi; 关于指针的迷惑&comma;我自己问的&period;

    来自:http://www.cnblogs.com/del/archive/2008/01/01/1022124.html -------------------------------------- ...