洛谷 P1960 列队

题意简述

有一个n × m 的矩阵，第i行第j列元素编号为（i - 1）× m +j
每次将一个数取出，其他元素依次向左，向上填补空缺，最后将取出的数放入矩阵最后一格
求每次取出数的编号

题解思路

由于最后一列较为特殊，只有当取出的数位于最后一列，向上填补空缺时才有影响，所有特殊考虑
对于每一行的（m - 1）个元素 和 最后一列元素都维护一个splay
进行删除第k个元素 和 在末尾插入元素 两个操作

代码

#include <cstdio>
#include <cassert>
using namespace std;
typedef long long ll;
struct Node
{
	ll l, r;
	Node *c[2];
	int s;
	Node() {l = r = 0; s = 0; c[0] = c[1] = 0; }
	Node(ll x) {l = r = x; s = 1; c[0] = c[1] = 0; }
	Node(ll l, ll r) {this -> l = l; this -> r = r; s = r - l + 1; c[0] = c[1] = 0; }
	int get(bool b){return c[b] ? c[b] -> s : 0; }
	void upt(){s = get(0) + get(1) + (r - l + 1); }
	int cmp(int x){return (x > get(0) && x <= get(0) + r - l + 1) ? -1 : x > get(0); }
}*r[300010];
int n, m, q, x, y;
void rtt(Node* &o, bool b)
{
	Node* t = o -> c[b ^ 1];
	o -> c[b ^ 1] = t -> c[b];
	t -> c[b] = o;
	o -> upt();
	t -> upt();
	o = t;
}
void splay(Node* &o, int k)
{
	if (!o) return;
	int d1 = o -> cmp(k);
	if (d1 == -1) return;
	int xx = k - d1 * (o -> s - o -> get(1));
	int d2 = o -> c[d1] -> cmp(xx);
	if (d2 == -1) rtt(o, d1 ^ 1);
	else 
	{
		splay(o -> c[d1] -> c[d2], xx - d2 * (o -> c[d1] -> s - o -> c[d1] -> get(1)));
		if (d1 == d2) rtt(o, d2 ^ 1);
		else rtt(o -> c[d1], d2 ^ 1);
		rtt(o, d1 ^ 1);
	}
}
void ins(Node* &o, Node* x)
{
	if (!o) {o = x; return; }
	splay(o, o -> s);
	o -> c[1] = x;
	o -> upt();
}
Node* del(Node* &o, int k)
{
	splay(o, k);
	if (o -> l == o -> r)
	{
		Node* t = o;
		if (!o -> c[0]) o = o -> c[1];
		else
		{
			splay(o -> c[0], o -> get(0));
			o -> c[0] -> c[1] = o -> c[1];
			o = o -> c[0];
			o -> upt();
		}
		t -> s = 1;
		t -> c[0] = t -> c[1] = 0;
		return t;
	}
	ll xxx = o -> l + k - o -> get(0) - 1;
	Node* x = new Node(o -> l, xxx - 1);
	o -> l = xxx + 1;
	x -> c[0] = o -> c[0];
	o -> c[0] = x;
	x -> upt();
	o -> upt();
	return new Node(xxx);
}
int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (register int i = 1; i <= n; ++i)
	{
		r[i] = new Node((ll)(i - 1) * m + 1, (ll)i * m - 1);
		ins(r[0], new Node((ll)i * m));
	}
	for (register int i = 1; i <= q; ++i)
	{
		scanf("%d%d", &x, &y);
		Node* idx;
		if (y == m)
		{
			printf("%lld
", (idx = del(r[0], x)) -> l);
			ins(r[0], idx);
		}
		else
		{
			ins(r[x], del(r[0], x));
			printf("%lld
", (idx = del(r[x], y)) -> l);
			ins(r[0], idx);
		}
	}
}