BZOJ 3173: [Tjoi2013]最长上升子序列( BST + LIS )

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

--------------------------------------------------------------------

#include<bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; ++i)

#define clr(x, c) memset(x, c, sizeof(x))

#define foreach(i, x) for(__typeof(x.begin()) i = x.begin(); i != x.end(); i++)

using namespace std;

const int maxn = 100009;

struct Node {

Node *ch[2], *p;

int s, v;

inline void upd() {

s = ch[0]->s + ch[1]->s + 1;

}

inline void setc(Node* t, int d) {

ch[d] = t;

t->p =this;

}

inline bool d() {

return this == p->ch[1];

}

} pool[maxn], *pt = pool, *root, *null;

Node* newNode(int _ = 0) {

pt->v = _; pt->s = 1;

pt->ch[0] = pt->ch[1] = pt->p = null;

return pt++;

}

void rot(Node* t) {

Node* p = t->p;

int d = t->d();

p->p->setc(t, p->d());

p->setc(t->ch[d ^ 1], d);

t->setc(p, d ^ 1);

p->upd();

if(p == root) root = t;

}

void splay(Node* t, Node* f = null) {

while(t->p != f) {

if(t->p->p != f)

   t->d() != t->p->d() ? rot(t) : rot(t->p);

rot(t);

}

t->upd();

}

Node* select(int k) {

for(Node* t = root; ;) {

int s = t->ch[0]->s;

if(k == s) return t;

if(k > s)

   k -= s + 1, t = t->ch[1];

else

   t = t->ch[0];

}

}

void init() {

null = newNode();

null->ch[0] = null->ch[1] = null->p = null;

null->s = 0;

root = newNode(maxn);

root->setc(newNode(-maxn), 0);

root->upd();

}

int seq[maxn], N = 0, g[maxn], dp[maxn];

void dfs(Node* t) {

if(t == null) return;

dfs(t->ch[0]);

if(t->v != maxn && t->v != -maxn) seq[N++] = t->v;

dfs(t->ch[1]);

}

int main() {

freopen("test.in", "r", stdin);

init();

int n;

cin >> n;

rep(i, n) {

int v;

scanf("%d", &v);

Node *L = select(v), *R = select(v + 1);

splay(L); splay(R, L);

R->setc(newNode(i), 0);

R->upd(); L->upd();

   g[i] = maxn;

}

dfs(root);

rep(i, n) {

int p = lower_bound(g, g + n, seq[i]) - g;

dp[seq[i]] = p + 1;

g[p] = seq[i];

}

int ans = 0;

rep(i, n) {

   ans = max(ans, dp[i]);

printf("%d\n", ans);

}

return 0;

}

--------------------------------------------------------------------

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

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 806  Solved: 432
[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