P3960 [NOIP 2017 提高组] 列队题解

本文提供一种动态开点线段树做法。

这道题写的时候调了很久，原因是 while(q--)，而处理询问时又用到了 $q$ 。

另外，sjx 在讲义中这样写：

为了解决空间问题，我们可以离线所有查询、删除和追加操作，然后 one by one 用线段树处理每个序列，每一个处理完后回滚到初始状态，再处理下一个。

为了解决空间问题，直接动态开点不就是了。

我们发现，每一行是相对独立的，所以考虑单独处理。对于每一行的前

m - 1

个元素与最后一列，我们需要维护单点查询、单点删除与末尾插入。暴力的单点删除显然不可取，那么容易想到用线段树标记每个元素是否已被删除，查询时用线段树二分找到被查询元素的真实位置。由于有末尾插入的操作，所以我们可以对每棵线段树先多开

q

个位置。对于新加入的元素，我们并不把它实际地插入到线段树中，而是放到这一行（或列）对应的一个 vector 里面。

具体地，对于一次操作，需要进行以下操作（假设

y \ne m

）：

在第 $x$ 棵线段树上二分找到 $a_{x, y}$ 的真实位置，从而得到 $a_{x, y}$ 的值（并输出）；
将 $a_{x, y}$ 插入到第 $n + 1$ 棵线段树（用于维护最后一列）的末尾；
从第 $x$ 棵线段树中删除 $a_{x, y}$ ；
在第 $n + 1$ 棵线段树上二分找到 $a_{x, m}$ 的位置，从而得到 $a_{x, m}$ 的值；
将 $a_{x, m}$ 插入到第 $x$ 棵线段树的末尾；
从第 $n + 1$ 棵线段树中删除 $a_{x, m}$ 。

y = m

时也类似，不再展开阐述。

时间复杂度

O(q \log n)

。

关于线段树节点数量，估算下来理论上限是

1.2 \times 10^7

，而实测下来

4 \times 10^6

已经足够了。

在代码实现中，线段树中的 0 指未被删除，1 指已被删除，这样处理的目的是在末尾插入元素时不需要访问线段树元素。

由于每个询问一定有解，所以线段树二分时没必要判断无解，整个过程也不需要考虑下标越界的问题，没什么细节，个人认为比较好写。

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, q, x, y, rt[300005], ps, val;
vector<int> num[300005];
struct Segtree {
	int tr[4000005], ls[4000005], rs[4000005], cnt;
	void update(int l, int r, int& p, int s) {
		if(!p) p = ++cnt;
		if(l == r) return tr[p] = 1, void();
		int mid = (l + r) >> 1;
		if(s <= mid) update(l, mid, ls[p], s);
		else update(mid + 1, r, rs[p], s);
		tr[p] = tr[ls[p]] + tr[rs[p]];
		return;
	}
	int query(int l, int r, int& p, int d) {
		if(!p) p = ++cnt;
		if(l == r) return l;
		int mid = (l + r) >> 1, tmp = (mid - l + 1) - tr[ls[p]];
		if(d > tmp) return query(mid + 1, r, rs[p], d - tmp);
		else return query(l, mid, ls[p], d);
	}
} tr;

signed main() {
	scanf("%lld %lld %lld", &n, &m, &q);
	for(int _ = 1; _ <= q; ++_) {
		scanf("%lld %lld", &x, &y);
		if(y < m) {
			ps = tr.query(1, m - 1 + q, rt[x], y); // step 1
			if(ps < m) val = (x - 1) * m + ps;
			else val = num[x][ps - m];
			printf("%lld\n", val);
			num[n + 1].push_back(val); // step 2
			tr.update(1, m - 1 + q, rt[x], ps); // step 3
			ps = tr.query(1, n + q, rt[n + 1], x); // step 4
			if(ps <= n) val = ps * m;
			else val = num[n + 1][ps - n - 1];
			num[x].push_back(val); // step 5
			tr.update(1, n + q, rt[n + 1], ps); // step 6
		}
		else {
			ps = tr.query(1, n + q, rt[n + 1], x); // step 1
			if(ps <= n) val = ps * m;
			else val = num[n + 1][ps - n - 1];
			printf("%lld\n", val);
			num[n + 1].push_back(val); // step 2
			tr.update(1, n + q, rt[n + 1], ps); // step 3
		}
	}
	return 0;
}

P3960 [NOIP 2017 提高组] 列队题解

文章操作

相关推荐

评论

P3960 [NOIP 2017 提高组] 列队题解