Problem – C – Codeforces

题意：有一个长为 $n$ （$n \le 10^6$）的序列，有两种操作：

1. 加入一个服务生，他可以为 $[l, r]$ 提供服务
2. 询问所有能为 $[l, r]$ 中任何位置提供服务（也就是区间有交）的服务生中最晚加入的那个，输出服务生的名字并把他删除

操作数不多于 $2 \times 10^5$。

区间有交的限制条件确实可以转化成 $l_i \le r_j$ 且 $r_i \ge l_j$ 的二维限制，但是实际上是完全没有必要的。

直接维护一棵线段树，每个结点上有完全覆盖了当前区间和与当前区间有交两种标记。查询的时候显然对路过的所有结点只能取完全覆盖了它的那些服务生，而对停止递归时的那个结点才可以取与当前区间有交的服务生。

因为要删除，用一个栈维护就行了，删除的时候打个标记懒删除。代码其实很短，并且跑的也很快。

教训：“跟区间有交”的限制一般都只需要一个 $\log$，尽量不要往树套树去想。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = (1 << 21) + 5;

vector<int> u[maxn], v[maxn];

int s, t, d;

void modify(int l, int r, int o) {
	v[o].push_back(d);

	if (s <= l && t >= r) {
		u[o].push_back(d);
		return;
	}

	int mid = (l + r) / 2;

	if (s <= mid)
		modify(l, mid, o * 2);
	if (t > mid)
		modify(mid + 1, r, o * 2 + 1);
}

bool removed[maxn];

int query(int l, int r, int o) {
	while (!u[o].empty() && removed[u[o].back()])
		u[o].pop_back();
	
	// int mid = (l + r) / 2;

	int ans = u[o].empty() ? 0 : u[o].back();

	if (s <= l && t >= r) {
		while (!v[o].empty() && removed[v[o].back()])
			v[o].pop_back();
		
		if (!v[o].empty())
			ans = max(ans, v[o].back());
		
		return ans;
	}

	int mid = (l + r) / 2;
	
	if (s <= mid)
		ans = max(ans, query(l, mid, o * 2));
	if (t > mid)
		ans = max(ans, query(mid + 1, r, o * 2 + 1));
	
	return ans;
}

char str[maxn][25];

int main() {
	strcpy(str[0], ">_<");

	int n, m;
	scanf("%d%d", &n, &m);

	for (int k = 1; k <= m; k++) {
		int op;
		scanf("%d", &op);

		if (op == 1) {
			scanf("%s%d%d", str[k], &s, &t);

			d = k;
			modify(0, n - 1, 1);
		}
		else {
			scanf("%d%d", &s, &t);

			int i = query(0, n - 1, 1);

			printf("%s\n", str[i]);

			if (i)
				removed[i] = true;
		}
	}

	return 0;
}