「BZOJ3173」[TJOI2013] 最长上升子序列
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
0 0 2
Sample Output
1
1
2
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
题解
题解
用treap维护序列后直接求lis
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define eps 1e-8 #define inf 1000000000 #define rad 100000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int 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; } int n,cnt,root,now,mx; int mn[100005],ans[100005]; int v[100005],size[100005],rnd[100005],l[100005],r[100005]; void update(int x) { size[x]=size[l[x]]+size[r[x]]+1; } void rturn(int &k) { int t=l[k];l[k]=r[t];r[t]=k;update(k);update(t);k=t; } void lturn(int &k) { int t=r[k];r[k]=l[t];l[t]=k;update(k);update(t);k=t; } void insert(int &x,int rank) { if(!x) { x=++cnt; rnd[x]=rand();size[x]=1; return; } size[x]++; if(size[l[x]]<rank) { insert(r[x],rank-size[l[x]]-1); if(rnd[r[x]]<rnd[x])lturn(x); } else { insert(l[x],rank); if(rnd[l[x]]<rnd[x])rturn(x); } } void dfs(int x) { if(!x)return; dfs(l[x]); v[++now]=x; dfs(r[x]); } void solve() { memset(mn,127,sizeof(mn)); mn[0]=-inf; for(int i=1;i<=n;i++) { int t=upper_bound(mn,mn+mx+1,v[i])-mn; if(mn[t-1]<=v[i]) { mn[t]=min(mn[t],v[i]); ans[v[i]]=t; mx=max(t,mx); } } } int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); insert(root,x); } dfs(root); solve(); for(int i=1;i<=n;i++) { ans[i]=max(ans[i-1],ans[i]); printf("%d\n",ans[i]); } return 0; } |
计数器 9861714
OI 课件=>
OI 课件=>
第74行的判断好像并没有什么用。。。
根据upper_bound的定义好像mn
可以直接赋为v 
呢。。
if(mn[t-1]<=v
)
好像这句没用吧= =
神犇求加友链
神犇求加友链
跪！！