「NOIP2017」列队 数据结构

发表于 更新于 分类于

「NOIP2017」列队

这题做法比较多，感觉平衡树的写法应该比较简单。

虽然常数会比较大。

我们分别维护每一行和最后一列的元素。

对于每次操作的二元组\((x,y)\)

  1. 如果\(y=m\)，就把元素移到列末尾。

  2. 否则，行内删除该元素，把最后一列第\(x\)个元素移到行末尾并删除，之后把\((x,y)\)移动到列末尾。

查询很简单，查一下第\(k\)大的编号就是了。

但是有一个问题，这样开的点会非常多，空间根本开不下。

所以要向方伯伯的OJ那题那样，把连续的编号压缩一下，用到的时候再拆开。

和珂朵莉树思想应该是一样的。

具体实现的时候，因为会涉及拆开一个点的操作，所以把那个要用的点单独拿出来比较好。

所以分裂的时候按子树大小分裂(相当于按排名)分成三部分\(a,b,c\)，其中\(b\)恰好是第\(k\)名。

具体实现看代码吧！

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
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 3e5 + 5;
int n, m, Q, root[N], tot;
struct node {
	int v, cnt, siz, lc, rc, rnd;
} t[N * 5];

int newnode(int v, int cnt) {
	if (!cnt) return 0;
    t[++tot].rnd = rand();
    t[tot].v = v;
    t[tot].cnt = cnt;
    t[tot].siz = cnt;
    return tot;
}
void pushup(int p) {
	t[p].siz = t[t[p].lc].siz + t[t[p].rc].siz + t[p].cnt;
}
void split(int p, int &x, int &y, int &z, int k) {
	if (!p) {
		x = y = z = 0;
		return;
	}
	if (k <= t[t[p].lc].siz) {
		z = p;
		split(t[p].lc, x, y, t[p].lc, k);
	} else {
		k -= t[t[p].lc].siz;
		if (k <= t[p].cnt) {
			y = p;
			x = t[p].lc;
			z = t[p].rc;
			t[p].lc = t[p].rc = 0;
		} else {
			x = p;
			k -= t[p].cnt;
			split(t[p].rc, t[p].rc, y, z, k);
		}
	}
	pushup(p);
}
int merge(int x, int y) {
    if (x == 0 || y == 0) return x + y;
    if (t[y].rnd > t[x].rnd) {
        t[x].rc = merge(t[x].rc, y);
        pushup(x);
        return x;
    } else {
    	t[y].lc = merge(x, t[y].lc);
    	pushup(y);
    	return y;
    }
}

signed main() {
	srand(1919810);
    scanf("%lld %lld %lld", &n, &m, &Q);
    for (int i = 1; i <= n; i++) {
    	root[i] = newnode((i - 1) * m + 1, m - 1);
    	root[0] = merge(root[0], newnode(m * i, 1));
    }
    while (Q--) {
    	int x, y;
    	scanf("%lld %lld", &x, &y);
    	if (y == m) {
            int a, b, c;
            split(root[0], a, b, c, x);
            printf("%lld\n", t[b].v);
            root[0] = merge(merge(a, c), b);
    	} else {
    		int a, b, c;
    		split(root[0], a, b, c, x);
    		root[x] = merge(root[x], b);
    		root[0] = merge(a, c);
    		split(root[x], a, b, c, y);
    		y -= t[a].siz;
    		root[0] = merge(root[0], newnode(t[b].v + y - 1, 1));
    		printf("%lld\n", t[b].v + y - 1);
            int l = y - 1, r = t[b].cnt - y;
            b = merge(newnode(t[b].v, l), newnode(t[b].v + y, r));
            root[x] = merge(a, merge(b, c));
    	}
    }
    return 0;
}