自动搬运

查看原文

来自洛谷，原作者为

	lzyqwq 我永远喜欢数据结构。

搬运于2025-08-24 23:12:38，当前版本为作者最后更新于2025-04-09 13:51:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给定 $n,m$，你需要维护一个 $[1,n)$ 的数轴上区间的初始为空的可重集合，支持三种操作共 $m$ 次：

1. 插入一个区间 $[l,r)$。
2. 删除第 $t$ 次操作插入的区间。
3. 给出一个区间 $[l,r)$，判断当前可重集合中是否存在一个子集，使得子集中所有区间的并恰好是 $[l,r)$。

将区间看成四元组 $(l_i,r_i,b_i,e_i)$，将询问看成三元组 $(x_j,y_j,t_j)$。

首先区间都是左闭右开的实数区间。考虑记第 $i$ 个段为 $[i,i+1)$，则区间 $[l,r)$ 表示了第 $l,\dots ,r-1$ 个段。所以令 $r\leftarrow r-1$ 后，仅需要考虑整数的情况。下面令 $[l,r]$ 表示该区间内整数构成的集合。

判断一个询问时，贪心地把所有子集选上再判断是否有解。这样一定不劣。

分治。记当前分治区间为 $[L,R]$，中点 $M=\left\lfloor\dfrac{L+R}{2}\right\rfloor$。考虑解决所有 $x_j\le M<y_j$ 的询问。

先考虑选上所有跨过 $l_i\le M<r_i$ 且 $[l_i,r_i]\sube [x_j,y_j]$ 的区间。选上这些子区间后并集形如一个跨过 $M$ 的区间 $[\text{lp}_j,\text{rp}_j]$，其中 $\text{lp}_j,\text{rp}_j$ 表示左半区间中被覆盖的最小位置、有半区间中被覆盖的最大位置。考虑求出她们。

以 $\text{lp}_j$ 为例。记 $k_w=\min\limits_{l_i=w,r_i>M}r_i$。按照时间维扫描线，则相当于在 $b_i$ 时刻插入一个区间、在 $e_i+1$ 时刻删除一个区间；查询 $t_j$ 时刻 $[x_j,M]$ 内最小的 $p$ 使得 $k_p\le y_j$。记 可重集 $K_w=\{r_i\,|\,l_i=w,r_i>M\}$，则 $k_w$ 就是 $K_w$ 中的最小值。问题变成维护 $n$ 个可重集，支持单个可重集插入、删除元素，求一个区间内最小值不超过某个定值的编号最小的可重集。用线段树维护，叶子节点维护 multiset，非叶子节点维护区间内 $k_w$ 的最小值。查询使用线段树二分。单次时间复杂度 $\mathcal{O}(\log n)$。

接下来考虑不跨过 $M$ 的子集。对于每个询问求出 $\text{Lp}_j,\text{Rp}_j$，表示左 / 右半区间的子集最小 / 最大不能覆盖的位置。

同样以 $\text{Lp}_j$ 为例，考虑从左往右扫描答案 $p$。则对于一个询问，若插入所有 $x_j\le l_i\le p,r_i\le M$ 的区间后，$p$ 位置仍未被覆盖，则她不会被后面的区间覆盖了。因此扫到的第一个符合上述条件的 $p$ 即为答案。每次暴力找出 $p$ 能更新的询问，然后将这些询问扔掉。则一个询问只会被计算一次。将询问的时刻离散化，对时间轴用线段树维护 $f_t$ 表示 $t$ 时刻的询问扫到当前 $p$ 时的 $\text{Lp}_j$，由于在之前已经把 $\text{Lp}_j<p$ 的询问取出了，剩下的询问保证 $f_t\ge p$，维护最小值，判断当前 $f_t$ 最小值是否为 $p$，暴力取出最小值再删除即可。先不考虑 $x_j\le l_i$。此时仅要求 $L\le l_i$。那么扫描的时候插入所有 $l_i=p$ 的区间，其影响为对 $[b_i,e_i]$ 时刻内的区间的 $f_t$ 对 $r_i+1$ 取 $\max$。在线段树上打标记即可。接下来考虑 $x_j\le l_i$ 的限制，则扫到 $p$ 时对于 $x_j=p$ 的询问，之前的修改不能生效，且这个区间不能在这之前被取出。后者考虑初值赋为极大值即可，前者考虑在扫到 $p$ 时单点重新覆盖成 $p$ 即可消除先前的标记。容易线段树维护。

最后判断有无解就是是否 $\text{Lp}_j\ge \text{lp}_j$ 且 $\text{Rp}_j\le \text{rp}_j$。就是考虑两边能否和中间连上。

一个询问在第一个跨过中点的区间被计算，一个区间在包含她的 $\mathcal{O}(\log n)$ 个分治区间中被操作。因此时间复杂度 $\mathcal{O}\left(m\log^2n+n\log n\right)$，空间复杂度视实现精细程度为 $\mathcal{O}(n)$ 或 $\mathcal{O}(m\log n)$。

之前的代码有些细节问题，现在修了一下。

#include <bits/stdc++.h>
#define eb emplace_back
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
using namespace std; const int N = 1000005; vector<int> l_[N], r_[N];
struct QR { int l, r, t; }; vector<QR> qr, Qr, Rg, gl[N], gr[N];
struct RG { int l, r, tl, tr; }; vector<RG> rg; bool ans[N], ok[N];
int n, q, l[N], r[N], lp[N], rp[N], Lp[N], Rp[N], lh[N], c, op[N];
struct SGT1 {
	multiset<int> s[N]; int t[N << 1]; SGT1 () { fill(t, t + (N << 1), N); }
	void U(int x, int l, int r, int k, int v, bool o) {
		if (l == r) {
			if (o) s[l].emplace(v); else s[l].erase(s[l].find(v));
			return void(t[x] = s[l].size() ? *s[l].begin() : N);
		}
		int m = l + r >> 1;
		if (k <= m) U(ls(m), l, m, k, v, o); else U(rs(m), m + 1, r, k, v, o);
		t[x] = min(t[ls(m)], t[rs(m)]);
	}
	int Q(int x, int l, int r, int ql, int qr, int v) {
		if (t[x] > v) return 0; if (l == r) return l; int m = l + r >> 1, k = 0;
		if (ql <= m) k = Q(ls(m), l, m, ql, qr, v); if (k) return k;
		return Q(rs(m), m + 1, r, ql, qr, v);
	}
} t1;
struct SGT2 {
	multiset<int> s[N]; int t[N << 1];
	void U(int x, int l, int r, int k, int v, bool o) {
		if (l == r) {
			if (o) s[l].emplace(v); else s[l].erase(s[l].find(v));
			return void(t[x] = s[l].size() ? *s[l].rbegin() : 0);
		}
		int m = l + r >> 1;
		if (k <= m) U(ls(m), l, m, k, v, o); else U(rs(m), m + 1, r, k, v, o);
		t[x] = max(t[ls(m)], t[rs(m)]);
	}
	int Q(int x, int l, int r, int ql, int qr, int v) {
		if (t[x] < v) return 0; if (l == r) return l; int m = l + r >> 1, k = 0;
		if (qr > m) k = Q(rs(m), m + 1, r, ql, qr, v); if (k) return k;
		return Q(ls(m), l, m, ql, qr, v);
	}
} t2;
struct SGT3 {
	int s[N << 1], t[N << 1];
	void B(int x, int l, int r) {
		s[x] = N; t[x] = 0; if (l == r) return;
		int m = l + r >> 1; B(ls(m), l, m); B(rs(m), m + 1, r);
	}
	void U(int x, int v) { s[x] = max(s[x], v); t[x] = max(t[x], v); }
	void U(int x, int l, int r, int ql, int qr, int v) {
		if (ql <= l && r <= qr) return U(x, v); int m = l + r >> 1; 
		if (ql <= m) U(ls(m), l, m, ql, qr, v);
		if (qr > m) U(rs(m), m + 1, r, ql, qr, v);
		s[x] = max(min(s[ls(m)], s[rs(m)]), t[x]);
	}
	void C(int x, int l, int r, int k, int v) {
		if (l == r) return void(s[x] = v); int m = l + r >> 1;
		U(ls(m), t[x]); U(rs(m), t[x]); t[x] = 0;
		if (k <= m) C(ls(m), l, m, k, v); else C(rs(m), m + 1, r, k, v);
		s[x] = min(s[ls(m)], s[rs(m)]);
	}
	int Q(int x, int l, int r) {
		if (l == r) return l; int m = l + r >> 1;
		return s[ls(m)] < s[rs(m)] ? Q(ls(m), l, m) : Q(rs(m), m + 1, r);
	}
} t3;
struct SGT4 {
	int s[N << 1], t[N << 1];
	void B(int x, int l, int r) {
		s[x] = 0; t[x] = N; if (l == r) return;
		int m = l + r >> 1; B(ls(m), l, m); B(rs(m), m + 1, r);
	}
	void U(int x, int v) { s[x] = min(s[x], v); t[x] = min(t[x], v); }
	void U(int x, int l, int r, int ql, int qr, int v) {
		if (ql <= l && r <= qr) return U(x, v); int m = l + r >> 1; 
		if (ql <= m) U(ls(m), l, m, ql, qr, v);
		if (qr > m) U(rs(m), m + 1, r, ql, qr, v);
		s[x] = min(max(s[ls(m)], s[rs(m)]), t[x]);
	}
	void C(int x, int l, int r, int k, int v) {
		if (l == r) return void(s[x] = v); int m = l + r >> 1;
		U(ls(m), t[x]); U(rs(m), t[x]); t[x] = N;
		if (k <= m) C(ls(m), l, m, k, v); else C(rs(m), m + 1, r, k, v);
		s[x] = max(s[ls(m)], s[rs(m)]);
	}
	int Q(int x, int l, int r) {
		if (l == r) return l; int m = l + r >> 1;
		return s[ls(m)] > s[rs(m)] ? Q(ls(m), l, m) : Q(rs(m), m + 1, r);
	}
} t4;
void lzyqwq(int l, int r, vector<QR> &qr, vector<RG> &rg) {
	if (!qr.size() || !rg.size()) return;
	if (l == r) {
		for (RG i : rg) Rg.eb(QR{i.l, i.r, i.tl}), Rg.eb(QR{-i.l, i.r, i.tr + 1});
		stable_sort(qr.begin(), qr.end(), [&](QR u, QR v) { return u.t < v.t; });
		stable_sort(Rg.begin(), Rg.end(), [&](QR u, QR v) { return u.t < v.t; });
		for (int i = 0, j = 0, d = 0; i < qr.size(); ++i) {
			for (; j < Rg.size() && Rg[j].t <= qr[i].t; ++j)
				d += abs(Rg[j].l) / Rg[j].l;
			ans[qr[i].t] = (d > 0);
		}
		qr.clear(); rg.clear(); Rg.clear(); return;
	}
	int m = l + r >> 1; c = 0;
	for (QR i : qr)
		if (i.l <= m && i.r > m) {
			Qr.eb(i); Lp[i.t] = m + 1; Rp[i.t] = m; lh[++c] = i.t;
		}
	if (c) {
		for (RG i : rg)
			if (i.l <= m && i.r > m)
				Rg.eb(QR{i.l, i.r, i.tl}), Rg.eb(QR{-i.l, i.r, i.tr + 1});
		stable_sort(Qr.begin(), Qr.end(), [&](QR u, QR v) { return u.t < v.t; });
		stable_sort(Rg.begin(), Rg.end(), [&](QR u, QR v) { return u.t < v.t; });
		for (int i = 0, j = 0; i < c; ++i) {
			for (; j < Rg.size() && Rg[j].t <= Qr[i].t; ++j)
				t1.U(1, 1, n, abs(Rg[j].l), Rg[j].r, abs(Rg[j].l) == Rg[j].l);
			lp[Qr[i].t] = t1.Q(1, 1, n, Qr[i].l, n, Qr[i].r);
			if (!lp[Qr[i].t]) lp[Qr[i].t] = m + 1;
			if (i == c - 1)
				for (--j; j >= 0; --j)
					t1.U(1, 1, n, abs(Rg[j].l), Rg[j].r, abs(Rg[j].l) != Rg[j].l);
		}
		for (int i = 0, j = 0; i < c; ++i) {
			for (; j < Rg.size() && Rg[j].t <= Qr[i].t; ++j)
				t2.U(1, 1, n, Rg[j].r, abs(Rg[j].l), abs(Rg[j].l) == Rg[j].l);
			rp[Qr[i].t] = t2.Q(1, 1, n, 1, Qr[i].r, Qr[i].l);
			if (!rp[Qr[i].t]) rp[Qr[i].t] = m;
			if (i == c - 1)
				for (--j; j >= 0; --j)
					t2.U(1, 1, n, Rg[j].r, abs(Rg[j].l), abs(Rg[j].l) != Rg[j].l);
		}
		for (int i = 0; i < c; ++i)
			l_[Qr[i].l].eb(i + 1), r_[Qr[i].r].eb(i + 1), lh[i + 1] = Qr[i].t;
		Qr.clear(); Rg.clear(); t3.B(1, 1, c); t4.B(1, 1, c);
		for (auto [l, r, tl, tr] : rg) {
			if (l <= m && r > m) continue;
			int sl = lower_bound(lh + 1, lh + c + 1, tl) - lh,
			    sr = upper_bound(lh + 1, lh + c + 1, tr) - lh - 1;
			if (sl > sr) continue;
			if (r <= m) gl[l].eb(QR{sl, sr, r + 1});
			else gr[r].eb(QR{sl, sr, l - 1});
		}
		for (int i = l, p; i <= m; ++i) {
			for (int j : l_[i]) t3.C(1, 1, c, j, i); l_[i].clear();
			for (auto [l, r, v] : gl[i]) t3.U(1, 1, c, l, r, v); gl[i].clear();
			while (t3.s[1] == i) Lp[lh[p = t3.Q(1, 1, c)]] = i, t3.C(1, 1, c, p, N);
		}
		for (int i = r, p; i > m; --i) {
			for (int j : r_[i]) t4.C(1, 1, c, j, i); r_[i].clear();
			for (auto [l, r, v] : gr[i]) t4.U(1, 1, c, l, r, v); gr[i].clear();
			while (t4.s[1] == i) Rp[lh[p = t4.Q(1, 1, c)]] = i, t4.C(1, 1, c, p, 0);
		}
		for (QR i : qr)
			if (i.l <= m && i.r > m)
				ans[i.t] = (lp[i.t] <= Lp[i.t] && rp[i.t] >= Rp[i.t]);
	}
	vector<QR> l_, r_; vector<RG> L_, R_;
	for (QR i : qr) if (i.r <= m) l_.eb(i); else if (i.l > m) r_.eb(i);
	for (RG i : rg) if (i.r <= m) L_.eb(i); else if (i.l > m) R_.eb(i);
	qr.clear(); rg.clear(); lzyqwq(l, m, l_, L_); lzyqwq(m + 1, r, r_, R_);
	l_.clear(); r_.clear(); L_.clear(); R_.clear();
}
int main() {
	scanf("%d%d", &n, &q); --n;
	for (int i = 1; i <= q; ++i) {
		scanf("%d%d", &op[i], &l[i]);
		if (op[i] == 1) scanf("%d", &r[i]);
		else if (op[i] ^ 3)
			rg.eb(RG{l[l[i]], r[l[i]] - 1, l[i], i - 1}), ok[l[i]] = 1;
		else scanf("%d", &r[i]), qr.eb(QR{l[i], r[i] - 1, i});
	}
	for (int i = 1; i <= q; ++i)
		if (op[i] == 1 && !ok[i]) rg.eb(RG{l[i], r[i] - 1, i, q});
	lzyqwq(1, n, qr, rg);
	for (int i = 1; i <= q; ++i) if (op[i] == 3) puts(ans[i] ? "Y" : "N"); return 0;
}