题解：P12082 [Ynoi1998] Frühlingsbeginn

lzyqwq · 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;
}