洛谷P3960 列队(动态开节点线段树)

时间：2021-09-15 02:52:37

题意

题目链接

Sol

看不懂splay。。，看不懂树状数组。。。

只会暴力动态开节点线段树

观察之后不难发现，我们对于行和列需要支持的操作都是相同的：找到第\(k\)大的元素并删除，在末尾插入一个元素

这样我们可以维护\(n+1\)棵线段树(对列单独建一棵)

每次操作的时候，如果\(y_i = m\)，那么只对列所在的线段树进行操作

否则，首先在第\(x_i\)棵线段树中找到第\(y_i\)大的元素并删除，在列所在的线段树中找到需要插入的元素并记录下来。

然后再删除列中对应的元素

当然，还有许多很巧妙的操作。

  1. 对于没有被更改过的点，我们可以\(O(1)\)计算出它的编号。显然，被更改过的点不会太多，直接拿vector维护即可

  2. 开始时每个线段树上的对应节点的siz都是满的，所以对于没有更新过的区间，直接拿区间长度来获取siz即可

  3. 我们在查找到某个节点的时候同时也会删除它，因此查找和删除操作可以写到同一个函数中

#include<bits/stdc++.h>

#define LL long long int

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

char buf[1 << 23], *p1 = buf, *p2 = buf,  obuf[1 << 24], *O = obuf;

void print(LL x) {

    if(x > 9) print(x / 10);

    *O++= x % 10 + '0';

}

using namespace std;

const int MAXN = 3e5 + 10, SS = MAXN * 20;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0'|| c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M, Q, cnt, siz[SS], ls[SS], rs[SS], rt[MAXN], tot;

LL las[MAXN << 1];

vector<LL> pos[MAXN];

int Modify(int &k, int l, int r, int kth) {

	if(!k) k = ++tot, siz[k] = r - l + 1;  siz[k]--;

	if(l == r) return l;

	int mid = l + r >> 1, now = (!ls[k] ? mid - l + 1 : siz[ls[k]]);

	if(now < kth) return Modify(rs[k], mid + 1, r, kth - now);

	else return Modify(ls[k], l, mid, kth);

}

LL Query(int y, int x) {

	LL ans = 0;

	if(y == M) ans = las[Modify(rt[0], 1, N + Q, x)];

	else {

		int tmp = Modify(rt[x], 1, M + Q, y);

		if(tmp < M) ans = 1ll * (x - 1) * M + tmp;

		else ans = pos[x][tmp - M];

		pos[x].push_back(las[Modify(rt[0], 1, N + Q, x)]);

	}

	return las[++cnt] = ans;

}

int main() {

	N = read(); M = read(); Q = read();

	for(int i = 1; i <= N; i++) las[++cnt] = 1ll * i * M;

	for(int i = 1; i <= Q; i++) print(Query(read(), read())), *O++ = '\n';

    fwrite(obuf, O-obuf, 1 , stdout);

	return 0;

}

相关文章