[NOIP2017 D2 T3]列队（线段树/平衡树）

Posted on | In , ,
NOIP2017 Day2 T3 phalanx

题目

描述

Sylvia 是一个热爱学习的女♂孩子。
前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。
Sylvia 所在的方阵中有$n \times m$名学生，方阵的行数为 $n$，列数为 $m$。
为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中 的学生从 1 到 $n \times m$ 编上了号码（参见后面的样例）。即：初始时，第 $i$ 行第 $j$ 列 的学生的编号是$(i-1)\times m + j$。
然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了 $q$件这样的离队事件。每一次离队事件可以用数对$(x,y) (1 \le x \le n, 1 \le y \le m)$描述，表示第 $x$ 行第 $y$ 列的学生离队。
在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：

  1. 向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条 指令之后，空位在第 $x$ 行第 $m$ 列。
  2. 向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条 指令之后，空位在第 $n$ 行第 $m$ 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 $n$ 行 第 $m$ 列一个空位，这时这个学生会自然地填补到这个位置。
因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学 的编号是多少。
注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。

输入

输入共 $q+1$行。
第 1 行包含 3 个用空格分隔的正整数 $n, m, q$，表示方阵大小是 $n$ 行 $m$ 列，一共发 生了 $q$ 次事件。
接下来 $q$ 行按照事件发生顺序描述了 $q$ 件事件。每一行是两个整数 $x, y$，用一个空 格分隔，表示这个离队事件中离队的学生当时排在第 $x$ 行第 $y$ 列。

输出

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学 生的编号。

输入样例

1
2
3
4
2 2 3
1 1
2 2
1 2

输出样例

1
2
3
1
1
4

数据规模与约定

$n,m,q \leq 3 \times 10^5$
数据保证每一个事件满足 $1 \le x \le n,1 \le y \le m$

解题思路

一道数据结构的好题。
首先我们发现，每次操作只会更改某一行和最后一列的状态，那么我们可以单独把最后一列拿出来用一个数据结构维护，再用$n$个数据结构维护每一行的前$m-1$个元素。
那用什么数据结构好呢？

一、线段树

线段树是最容易想到的，共开$n+1$颗线段树，前$n$颗维护每行前$m-1$个元素，第$n+1$颗维护最后一列的元素。
每次对$(x,y)$操作都可以转化为一个基本操作：从一颗线段树里面拿出一个元素加到一颗线段树的末尾，具体来说：

  • 如果$y = m$，只需要从“列线段树”里拿出第$x$个元素加到它本身末尾
  • 否则，从第$x$颗“行线段树”里拿出第$y$个元素加到“列线段树”末尾，再从“列线段树”里拿出第$x$个元素加到“行线段树”末尾

所谓的“拿出”操作就是一个在线段树上二分查找的过程，为此我们要在线段树每个节点上记录一个size，表示当前节点表示的区间里面还剩多少个元素。
另外，每颗线段树要多开$q$的区间长度（想想操作过程就明白了）。

但是，以上并不是这道题的难点，这道题的特殊之处在于你无法直接开满$n+1$颗线段树！
怎么办呢，我们可以动态开点来解决，也就是说当你要用某个点时再开它（想想主席树）。这样我们只需要$NlogN$的空间就够了。

时间复杂度 $O(q\log (n+q))$

二、平衡树

既然线段树可以，平衡树当然也可以了！
同样的思路：每次操作都可以转化为从一颗平衡树上二分查找第k大的值，把它加到一颗平衡树的末尾。

怎么解决空间问题？由于有一些人至始至终都站在一起，我们可以在平衡树上只用一个节点表示这个区间$[l,r]$（编号从$l$到$r$的人），当我们发现这个区间中的某个人（如编号为$k$的人）要离队时，再把它split成两个小区间（$[l,k-1],[k+1,r]$），输出$k$，这样就能保证空间复杂度为 $NlogN$。

时间复杂度$O(q\log n)$

三、树状数组

有待学习…

Code#1（线段树）

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
#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 300005;
int n, m, q, qx, qy, p[N], root[N];
LL t;

struct segTree{
	int son[2];
	LL val, size;
}tr[N*30];

struct OPT_segTree{
	int cnt;
	inline int newNode(int l, int r, int kind){
		cnt++;
		int temp = (kind == 0 ? m - 1 : n);
		if(l <= temp && r <= temp)	tr[cnt].size = r - l + 1;
		else if(l <= temp && r > temp)		tr[cnt].size = temp - l + 1;
		else if(l > temp && r > temp)		tr[cnt].size = 0;
		return cnt;
	}
	inline void pushup(int id){
		tr[id].size = tr[tr[id].son[0]].size + tr[tr[id].son[1]].size;
	}
	LL getKth(int id, int l, int r, LL k, int kind){
		if(l == r){
			if(!tr[id].val){
				if(kind == 0)	tr[id].val = 1ll * (qx - 1) * m + l;
				else	tr[id].val = 1ll * l * m;
			}
			tr[id].size = 0;
			return tr[id].val;
		}
		int mid = (l + r) >> 1;
		if(!tr[id].son[0])	tr[id].son[0] = newNode(l, mid, kind);
		if(!tr[id].son[1])	tr[id].son[1] = newNode(mid+1, r, kind);
		LL res = 0;
		if(tr[tr[id].son[0]].size >= k)	res = getKth(tr[id].son[0], l, mid, k, kind);
		else	res = getKth(tr[id].son[1], mid+1, r, k - tr[tr[id].son[0]].size, kind);
		pushup(id);
		return res;
	}
	void insert(int id, int l, int r, int pos, LL val, int kind){
		if(l == r){
			tr[id].val = val;
			tr[id].size = 1;
			return;
		}
		int mid = (l + r) >> 1;
		if(!tr[id].son[0])	tr[id].son[0] = newNode(l, mid, kind);
		if(!tr[id].son[1])	tr[id].son[1] = newNode(mid+1, r, kind);
		if(pos <= mid)	insert(tr[id].son[0], l, mid, pos, val, kind);
		else	insert(tr[id].son[1], mid+1, r, pos, val, kind);
		pushup(id);
	}
}Seg;

int main(){
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= n; i++)	p[i] = m - 1;
	p[n+1] = n;
	for(int i = 1; i <= n; i++)	root[i] = Seg.newNode(1, m - 1 + q, 0);
	root[n+1] = Seg.newNode(1, n + q, 1);
	for(int i = 1; i <= q; i++){
		scanf("%d%d", &qx, &qy);
		if(qy == m){
			printf("%lld\n", t = Seg.getKth(root[n+1], 1, n + q, qx, 1));
			Seg.insert(root[n+1], 1, n + q, ++p[n+1], t, 1);
		}
		else{
			printf("%lld\n", t = Seg.getKth(root[qx], 1, m - 1 + q, qy, 0));
			Seg.insert(root[n+1], 1, n + q, ++p[n+1], t, 1);
			t = Seg.getKth(root[n+1], 1, n + q, qx, 1);
			Seg.insert(root[qx], 1, m - 1 + q, ++p[qx], t, 0);
		}
	}
	return 0;
}

Code#2（Splay）

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 300005;
int qx, qy, rt[N];
LL t, n, m, q;

struct Splay{
	int son[2], fa;
	LL val, l, r, size;
}tr[N*30];

struct OPT_Splay{
	int cnt;
	inline void pushup(int id){
		tr[id].size = tr[id].r - tr[id].l + 1;
		if(tr[id].son[0])	tr[id].size += tr[tr[id].son[0]].size;
		if(tr[id].son[1])	tr[id].size += tr[tr[id].son[1]].size;
	}
	inline int newNode(LL l, LL r){
		cnt++;
		tr[cnt].fa = tr[cnt].son[0] = tr[cnt].son[1] = 0;
		tr[cnt].size = (tr[cnt].r = r) - (tr[cnt].l = l) + 1;
		return cnt;
	}
	inline void rotate(int x, int kind){
		int y = tr[x].fa, z = tr[y].fa, A = tr[y].son[kind], B = tr[x].son[kind], C = tr[x].son[!kind];
		tr[x].son[kind] = y, tr[x].fa = z;
		tr[y].fa = x, tr[y].son[!kind] = B;
		tr[z].son[tr[z].son[1] == y] = x, tr[B].fa = y;
		pushup(y), pushup(x);
	}
	inline void splay(int &root, int x, int goal){
		if(x == goal)	return;
		while(tr[x].fa != goal){
			int y = tr[x].fa, z = tr[y].fa;
			int isrson1 = tr[y].son[1] == x, isrson2 = tr[z].son[1] == y;
			if(z == goal)	rotate(x, !isrson1);
			else{
				if(isrson1 == isrson2)	rotate(y, !isrson2);
				else	rotate(x, !isrson1);
				rotate(x, !isrson2);
			}
		}
		if(goal == 0)	root = x;
	}
	inline int selectLast(int &root){
		int now = root;
		while(tr[now].son[1])	now = tr[now].son[1];
		return now;
	}
	inline void insert(int &root, LL val){
		int temp = newNode(val, val);
		int pos = selectLast(root);
		tr[pos].son[1] = temp;
		tr[temp].fa = pos;
		splay(root, temp, 0);
	}
	LL split(int &root, int now, LL k){
		splay(root, now, 0);
		k += tr[now].l - 1;
		int temp = newNode(k+1, tr[now].r);
		tr[now].r = k - 1;
		if(!tr[now].son[1]){
			tr[now].son[1] = temp;
			tr[temp].fa = now;
		}
		else{
			tr[temp].son[1] = tr[now].son[1];
			tr[tr[temp].son[1]].fa = temp;
			tr[now].son[1] = temp;
			tr[temp].fa = now;
		}
		pushup(temp), pushup(now);
		return k;
	}
	inline LL getKth(int &root, LL k){
		int now = root;
		while(1){
			if(k <= tr[tr[now].son[0]].size)	now = tr[now].son[0];
			else{
				k -= tr[tr[now].son[0]].size;
				if(k <= tr[now].r - tr[now].l + 1)
					return split(root, now, k);
				else{
					k -= (tr[now].r - tr[now].l + 1);
					now = tr[now].son[1];
				}
			}
		}
	}
}BST;

int main(){
	scanf("%lld%lld%lld", &n, &m, &q);
	for(int i = 1; i <= n; i++)	rt[i] = BST.newNode((i - 1) * m + 1, i * m - 1);
	rt[n+1] = BST.newNode(m, m);
	for(int i = 2; i <= n; i++)	BST.insert(rt[n+1], i * m);
	while(q--){
		scanf("%d%d", &qx, &qy);
		if(qy == m){
			printf("%lld\n", t = BST.getKth(rt[n+1], qx));
			BST.insert(rt[n+1], t);
		}
		else{
			printf("%lld\n", t = BST.getKth(rt[qx], qy));
			BST.insert(rt[n+1], t);
			BST.insert(rt[qx], BST.getKth(rt[n+1], qx));
		}
	}
	return 0;
}