洛谷 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\n", (idx = del(r[0], x)) -> l);

			ins(r[0], idx);

		}

		else

		{

			ins(r[x], del(r[0], x));

			printf("%lld\n", (idx = del(r[x], y)) -> l);

			ins(r[0], idx);

		}

	}

}