题目链接：传送门

Description

Sylvia所在的方阵中有n×mn \times m名学生,方阵的行数为 nn,列数为 mm。

为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中的学生从 11 到 n×mn \times m 编上了号码(参见后面的样例)。即:初始时,第 ii 行第 jj 列的学生的编号是(i−1)×m+j(i - 1) \times m + j

然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天中,一共发生了 qq 件这样的离队事件。每一次离队事件可以用数对(x,y)(1≤x≤n,1≤y≤m)(x, y) (1\le x\le n,1\le y\le m)描述,表示第 xx 行第 yy 列的学生离队。

在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达这样的两条指令:

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

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后,下一个学生才能离队。

因此在每一个离队的学生要归队时,队伍中有且仅有第 nn 行第 m 列一个空位,这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学的编号是多少。

注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后方阵中同学的编号可能是乱序的。

Constraints

n,m,q≤3×105n,m,q\le 3\times10^5

Solution

考虑一次离队就是将这一行的中间某个数删掉加入最后一列的末尾，将最后一列的某个数删掉加入这一行的末尾

显然我们对于每一行和最后一列开一个Splay维护即可

但是如果直接建Splay的话显然会爆空间，我们可以把Splay中的每一个点代表一段连续的区间，然后操作的时候再分裂开来即可

Code

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 3e5 + 100;

int N, M, Q;
struct tree
{
	int ch[2], fa, idx, idy, size;
}Tree[Maxn * 10];
int cnt_all;
struct Splay
{
	int root;
/**/inline void push_up (int x) { Tree[x].size = Tree[Tree[x].ch[0]].size + Tree[Tree[x].ch[1]].size + Tree[x].idy - Tree[x].idx + 1;}
	inline int judge_dir (int x) { return Tree[Tree[x].fa].ch[1] == x; }
	inline void connect (int x, int f, int dir) { Tree[x].fa = f; Tree[f].ch[dir] = x; }
	inline void newnode (int idx, int idy, int f, int dir)
	{
		Tree[++cnt_all].idx = idx; Tree[cnt_all].idy = idy; 
		Tree[cnt_all].size = idy - idx + 1;
		connect (cnt_all, f, dir);
	}
	inline void rotate (int x)
	{
		int f = Tree[x].fa, dirx = judge_dir(x), anc = Tree[f].fa, dirf = judge_dir(f);
		connect(Tree[x].ch[dirx ^ 1], f, dirx); connect(x, anc, dirf); connect(f, x, dirx ^ 1);
		push_up(f), push_up(x);
	}
	inline void splay (int x, int y)
	{
		while (Tree[x].fa != y)
		{
			int f = Tree[x].fa, dirx = judge_dir(x), anc = Tree[f].fa, dirf = judge_dir(f);
			if (anc == y) rotate(x);
			else if (dirx == dirf) rotate(f), rotate(x);
			else rotate(x), rotate(x);
		}
		if (!y) root = x;
	}
	inline void insert (int idx, int idy) 
	{ 
		if (!root) { newnode (idx, idy, 0, 0); root = cnt_all; return ; }
		int now = root;
		while (Tree[now].ch[1]) now = Tree[now].ch[1];
		newnode(idx, idy, now, 1);
		splay(cnt_all, 0);
	}
	inline int find (int k)
	{
		int now = root;
		while (1)
		{
			int tmp = Tree[now].ch[0];
			if (Tree[tmp].size < k && k <= Tree[tmp].size + Tree[now].idy - Tree[now].idx + 1) { splay(now, 0); return now; }
			if (Tree[tmp].size >= k) now = Tree[now].ch[0];
			else k -= Tree[tmp].size + Tree[now].idy - Tree[now].idx + 1, now = Tree[now].ch[1];
		}
	}
	inline void del (int x)
	{
		splay(x, 0);
		if (!Tree[x].ch[0]) { root = Tree[x].ch[1]; Tree[Tree[x].ch[1]].fa = 0; return ; }
		int now = Tree[x].ch[0];
		while (Tree[now].ch[1]) now = Tree[now].ch[1];
		splay(now, x);
		root = now; Tree[now].fa = 0;
		connect(Tree[x].ch[1], now, 1);
		push_up(now);
	}
	inline int split (int pos, int val)
	{
		int x = find(pos);
		int save = Tree[x].idx + (pos - Tree[Tree[x].ch[0]].size) - 1;
		if (Tree[x].idx == Tree[x].idy) { del(x); return save; }
		if (pos != Tree[Tree[x].ch[0]].size + 1)
		{
			int tmp = Tree[x].idy;
/**/    	Tree[x].idy = val - 1;
			if (val + 1 > tmp) { push_up(x); return save;}
			if (!Tree[x].ch[1]) { newnode(val + 1, tmp, x, 1); push_up(x); splay(cnt_all, 0); return save; }
			int now = Tree[x].ch[1];
			while (Tree[now].ch[0]) now = Tree[now].ch[0];
			splay(now, x);
			newnode(val + 1, tmp, now, 0);
			push_up(now), push_up(x);
			splay(cnt_all, 0);
			return save;
		}
		int tmp = Tree[x].idx;
		Tree[x].idx = val + 1;
		if (val - 1 < tmp) { push_up(x); return save;}
		if (!Tree[x].ch[0]) { newnode(tmp, val - 1, x, 0); push_up(x); splay(cnt_all, 0); return save; }
		int now = Tree[x].ch[0];
		while (Tree[now].ch[1]) now = Tree[now].ch[1];
		splay(now, x);
		newnode(tmp, val - 1, now, 1);
		push_up(now), push_up(x);
		splay(cnt_all, 0);
		return save;
	}
	inline int query (int pos, int type)
	{
		int x = find(pos), tmp = Tree[x].idx + (pos - Tree[Tree[x].ch[0]].size) - 1;
		if (type) del(x);
		return tmp;
	}
}S[Maxn];

inline int Index (int x, int y) { return (x - 1) * M + y; }

main()
{
#ifdef hk_cnyali
	freopen("phalanx.in", "r", stdin);
	freopen("phalanx.out", "w", stdout);
#endif
	N = read(), M = read(), Q = read();
	for (int i = 1; i <= N; ++i)
		S[i].insert(Index(i, 1), Index(i, M - 1)), S[0].insert(Index(i, M), Index(i, M));
	while (Q--)
	{
		int x = read(), y = read();
/**/	if (y == M)
		{
			int tmp = S[0].query(x, 1);
			printf("%lld\n", tmp);
			S[0].insert(tmp, tmp);
		}
		else
		{
			int tmp1 = S[x].split(y, S[x].query(y, 0)), tmp2 = S[0].query(x, 1);
			printf("%lld\n", tmp1);
			S[x].insert(tmp2, tmp2); S[0].insert(tmp1, tmp1);
		}
	}
	return 0;
}

Debug

  • 39L: sizesize要加上idy−idx+1idy - idx+1
  • 103L: valval和pospos不要搞混，pospos是询问当前这一行的第pospos个，valval是当前询问位置的答案(值)
  • 148L: 要特判y=My=M的情况
  • 要开long long