[BZOJ3173][Tjoi2013]最长上升子序列

试题描述

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

输入

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

输出

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

输入示例

输出示例

数据规模及约定

100%的数据 n<=100000

题解

首先讲一下怎么找到插入的位置，不难发现输入的数 k 就是让我们找到一个位置使得该位置左边有 k 个数然后在这个位置上插入。这不就是“第 k 大数”问题么？

好的，在此基础之上，我们再在 treap 上维护一波子树最大权值即可。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

int read() {

    int x = 0, f = 1; char c = getchar();

    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

    return x * f;

}

#define maxn 100010

struct Node {

	int r, val, mx, siz;

	Node() {}

	Node(int _, int __): r(_), val(__) {}

} ns[maxn];

int rt, ToT, fa[maxn], ch[2][maxn];

void maintain(int o) {

	ns[o].mx = ns[o].val; ns[o].siz = 1;

	for(int i = 0; i < 2; i++) if(ch[i][o])

		ns[o].mx = max(ns[o].mx, ns[ch[i][o]].mx),

		ns[o].siz += ns[ch[i][o]].siz;

	return ;

}

void rotate(int u) {

	int y = fa[u], z = fa[y], l = 0, r = 1;

	if(z) ch[ch[1][z]==y][z] = u;

	if(ch[1][y] == u) swap(l, r);

	fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;

	ch[l][y] = ch[r][u]; ch[r][u] = y;

	maintain(y); maintain(u);

	return ;

}

void insert(int& o, int k, int val) {

	if(!o) {

		ns[o = ++ToT] = Node(rand(), val);

		return maintain(o);

	}

	int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;

	bool d = (k >= ls + 1);

	insert(ch[d][o], k - (ls + 1) * d, val); fa[ch[d][o]] = o;

	if(ns[ch[d][o]].r > ns[o].r) {

		int t = ch[d][o];

		rotate(t); o = t;

	}

	return maintain(o);

}

int Find(int o, int k) {

	if(!o) return 0;

	int lm = ch[0][o] ? ns[ch[0][o]].mx : 0, ls = ch[0][o] ? ns[ch[0][o]].siz : 0;

	if(k >= ls + 1) return max(max(lm, ns[o].val), Find(ch[1][o], k - ls - 1));

	return Find(ch[0][o], k);

}

int main() {

	int n = read();

	for(int i = 1; i <= n; i++) {

		int p = read(), v = Find(rt, p);

		insert(rt, p, v + 1);

		printf("%d\n", ns[rt].mx);

	}

	return 0;

}

替罪羊树版：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

    if(Head == Tail) {

        int l = fread(buffer, 1, BufferSize, stdin);

        Tail = (Head = buffer) + l;

    }

    return *Head++;

}

int read() {

    int x = 0, f = 1; char c = Getchar();

    while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

    while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

    return x * f;

}

#define maxn 100010

struct Node {

	int v, siz, mx;

	Node() {}

	Node(int _): v(_) {}

} ns[maxn];

int rt, ToT, fa[maxn], ch[maxn][2];

void maintain(int o) {

	ns[o].siz = 1; ns[o].mx = ns[o].v;

	for(int i = 0; i < 2; i++) if(ch[o][i])

		ns[o].siz += ns[ch[o][i]].siz,

		ns[o].mx = max(ns[o].mx, ns[ch[o][i]].mx);

	return ;

}

const double Bili = .6;

bool unbal(int o) {

	return max(ch[o][0] ? ns[ch[o][0]].siz : 0, ch[o][1] ? ns[ch[o][1]].siz : 0) > Bili * ns[o].siz;

}

int rb;

void insert(int& o, int k, int v) {

	if(!o) {

		ns[o = ++ToT] = Node(v);

		return maintain(o);

	}

	int ls = ch[o][0] ? ns[ch[o][0]].siz : 0;

	if(k < ls + 1) insert(ch[o][0], k, v), fa[ch[o][0]] = o;

	else insert(ch[o][1], k - ls - 1, v), fa[ch[o][1]] = o;

	maintain(o);

	if(unbal(o)) rb = o;

	return ;

}

int cntn, get[maxn];

void getnode(int o) {

	if(!o) return ;

	getnode(ch[o][0]);

	get[++cntn] = o;

	getnode(ch[o][1]);

	fa[o] = ch[o][0] = ch[o][1] = 0;

	return ;

}

void build(int& o, int l, int r) {

	if(l > r) return ;

	int mid = l + r >> 1; o = get[mid];

	build(ch[o][0], l, mid - 1); build(ch[o][1], mid + 1, r);

	if(ch[o][0]) fa[ch[o][0]] = o;

	if(ch[o][1]) fa[ch[o][1]] = o;

	return maintain(o);

}

void rebuild(int& o) {

	cntn = 0; getnode(o);

	build(o, 1, cntn);

	return ;

}

void Insert(int k, int v) {

	rb = 0; insert(rt, k, v);

	if(!rb) return ;

	int frb = fa[rb];

	if(!frb) rebuild(rt), fa[rt] = 0;

	else if(ch[frb][0] == rb) rebuild(ch[frb][0]), fa[ch[frb][0]] = frb;

	else rebuild(ch[frb][1]), fa[ch[frb][1]] = frb;

	return ;

}

int qmx(int o, int k) {

	if(!o) return 0;

	int ls = ch[o][0] ? ns[ch[o][0]].siz : 0, lm = ch[o][0] ? ns[ch[o][0]].mx : 0;

	if(k < ls + 1) return qmx(ch[o][0], k);

	return max(max(lm, ns[o].v), qmx(ch[o][1], k - ls - 1));

}

int main() {

	int n = read();

	for(int i = 1; i <= n; i++) {

		int pos = read(), tmp = qmx(rt, pos);

		Insert(pos, tmp + 1);

		printf("%d\n", qmx(rt, i + 1));

	}

	return 0;

}

巴特西

[BZOJ3173][Tjoi2013]最长上升子序列

最新文章

热门文章