题解：P11695 [JRKSJ ExR] 昼寝

· · 题解

这道题太深刻了，我必须要记录一下。

首先为了方便，把所有的区间都变成闭区间。用 (ql,qr,t) 表示时刻 t 的一次询问 [ql,qr]，同理用 (l,r,tl,tr) 表示时刻 [tl,tr] 内的一次操作 [l,r]。

对询问做猫树分治，假设现在的分治区间是 [l,r]，要处理跨过 mid 的询问。对于一个要处理的询问，可以把能影响它的操作分为三类：跨过 mid 的，被左半区间包含的，被右半区间包含的。

先考虑处理跨过 mid 的操作对询问的影响，我们希望用这些区间向中点两侧覆盖出尽量长的长度。比如要求向左最远覆盖到哪，则一个操作 (l,r,tl,tr) 能更新的询问 (ql,qr,t) 满足 [l,r]\subseteq[ql,qr] 且 t\in[tl,tr]。对时间进行扫描线，开一棵线段树对每个位置维护当前以它为左端点的操作最小的右端点，扫到操作就扔进线段树里（或从中删除），扫到询问相当于查询 [ql,mid] 里第一个 \le qr 的位置，线段树二分即可。

再考虑使用两边的区间能不能填满剩下的部分。同样以左边为例，我们希望对每个询问求出从左端点开始向右最远能填到哪。现在考虑对序列从左往右扫描线，使用数据结构维护每个询问向后填线段的过程。具体来说以时间为下标建线段树，维护每个时间的询问当前向右延申到哪，扫到一个询问就加入线段树并初始化成 ql，扫到一个操作相当于将一段时间区间内的询问对 r+1 取 \max。扫完一个位置 i 后，取出线段树上所有值为 i 的询问弹掉，因为这意味着这些询问在 i 这个位置断开了。

右边也是同理的，求出这些信息后容易判断一个询问的答案。每个操作区间会在分治树上的 O(\log n) 个点被用到，所以时间复杂度 O(m\log^2 n)。

代码马上就写。upd：写完了。

//大分治题，真牛
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx), end(Tx)
using pr = array<int, 2>;
template<typename T>void cmax(T &x, T y){x = max(x, y);}
template<typename T>void cmin(T &x, T y){x = min(x, y);}
const int N = 1e6 + 5, inf = 1e9;
int n, m, q, tag[N], ans[N];
int tim[N], covl[N], covr[N], tol[N], tor[N];
multiset<int> sl[N], sr[N];
struct oper{int l, r, tl, tr;}a[N];
struct que{int l, r, t, id;}b[N];
vector<oper> chg[N], ins[N], del[N]; vector<que> qry[N];
#define ls now << 1
#define rs now << 1 | 1
struct SegTree1{
    int mn[N << 2];
    void pushup(int now){mn[now] = min(mn[ls], mn[rs]);}
    void build(int l, int r, int now){
        mn[now] = inf;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls); build(mid + 1, r, rs);
    }
    void update(int p, int l, int r, int now){
        if(l == r) return mn[now] = sl[l].empty() ? inf : *sl[l].begin(), void();
        int mid = (l + r) >> 1;
        if(p <= mid) update(p, l, mid, ls);
        else update(p, mid + 1, r, rs);
        pushup(now);
    }
    int find(int x, int y, int v, int l, int r, int now){
        if(mn[now] > v) return -1;
        if(l == r) return l;
        int mid = (l + r) >> 1, res = -1;
        if(x <= mid && (res = find(x, y, v, l, mid, ls)) != -1) return res;
        return find(x, y, v, mid + 1, r, rs);
    }
}T1;
struct SegTree2{
    int mx[N << 2];
    void pushup(int now){mx[now] = max(mx[ls], mx[rs]);}
    void build(int l, int r, int now){
        mx[now] = 0;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls); build(mid + 1, r, rs);
    }
    void update(int p, int l, int r, int now){
        if(l == r) return mx[now] = sr[r].empty() ? 0 : *sr[r].rbegin(), void();
        int mid = (l + r) >> 1;
        if(p <= mid) update(p, l, mid, ls);
        else update(p, mid + 1, r, rs);
        pushup(now);
    }
    int find(int x, int y, int v, int l, int r, int now){
        if(mx[now] < v) return -1;
        if(l == r) return l;
        int mid = (l + r) >> 1, res = -1;
        if(y > mid && (res = find(x, y, v, mid + 1, r, rs)) != -1) return res;
        return find(x, y, v, l, mid, ls); 
    }
}T2;
struct SegTree3{
    pr mn[N << 2]; int tag[N << 2];
    void pushup(int now){mn[now] = min(mn[ls], mn[rs]);}
    void pusht(int now, int v){cmax(mn[now][0], v); cmax(tag[now], v);}
    void pushdown(int now){
        if(!tag[now]) return;
        pusht(ls, tag[now]); pusht(rs, tag[now]);
        tag[now] = 0;
    }
    void build(int l, int r, int now){
        mn[now] = {inf, 0}; tag[now] = 0;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls); build(mid + 1, r, rs);
    }
    void modify(int x, int y, int v, int l, int r, int now){
        if(x <= l && r <= y) return pusht(now, v);
        int mid = (l + r) >> 1; pushdown(now);
        if(x <= mid) modify(x, y, v, l, mid, ls);
        if(y > mid) modify(x, y, v, mid + 1, r, rs);
        pushup(now);
    }
    void update(int p, pr v, int l, int r, int now){
        if(l == r) return mn[now] = v, void();
        int mid = (l + r) >> 1; pushdown(now);
        if(p <= mid) update(p, v, l, mid, ls);
        else update(p, v, mid + 1, r, rs);
        pushup(now);
    }
}T3;
struct SegTree4{
    pr mx[N << 2]; int tag[N << 2];
    void pushup(int now){mx[now] = max(mx[ls], mx[rs]);}
    void pusht(int now, int v){cmin(mx[now][0], v); cmin(tag[now], v);}
    void pushdown(int now){
        if(tag[now] == inf) return;
        pusht(ls, tag[now]); pusht(rs, tag[now]);
        tag[now] = inf;
    }
    void build(int l, int r, int now){
        mx[now] = {-inf, 0}; tag[now] = inf;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls); build(mid + 1, r, rs);
    }
    void modify(int x, int y, int v, int l, int r, int now){
        if(x <= l && r <= y) return pusht(now, v);
        int mid = (l + r) >> 1; pushdown(now);
        if(x <= mid) modify(x, y, v, l, mid, ls);
        if(y > mid) modify(x, y, v, mid + 1, r, rs);
        pushup(now);
    }
    void update(int p, pr v, int l, int r, int now){
        if(l == r) return mx[now] = v, void();
        int mid = (l + r) >> 1; pushdown(now);
        if(p <= mid) update(p, v, l, mid, ls);
        else update(p, v, mid + 1, r, rs);
        pushup(now);
    }
}T4;
#undef ls
#undef rs
void solve(int l, int r, vector<oper> vop, vector<que> vqry){
    if(l >= r || vop.empty() || vqry.empty()) return;
    int mid = (l + r) >> 1;
    //分类询问，对时间离散化
    vector<oper> opl, opr, opm;
    vector<que> qryl, qryr, qrym;
    vector<int> num;
    for(auto t : vop){
        if(t.r <= mid) opl.push_back(t);
        else if(t.l > mid) opr.push_back(t);
        else opm.push_back(t);
    }
    for(auto t : vqry){
        if(t.r <= mid) qryl.push_back(t);
        else if(t.l > mid) qryr.push_back(t);
        else qrym.push_back(t);
    }
    for(auto t : vop) num.push_back(t.tl), num.push_back(t.tr);
    for(auto t : qrym) num.push_back(t.t);
    sort(range(num)); num.erase(unique(range(num)), num.end());
    auto F = [&](int x){return lower_bound(range(num), x) - num.begin() + 1;};
    vector<oper> dwnl = opl, dwnr = opr;
    for(auto &t : opl) t.tl = F(t.tl), t.tr = F(t.tr);
    for(auto &t : opm) t.tl = F(t.tl), t.tr = F(t.tr);
    for(auto &t : opr) t.tl = F(t.tl), t.tr = F(t.tr);
    for(auto &t : qrym) tim[t.id] = t.t = F(t.t);
    int tot = num.size();
    //从 mid 开始，向两边覆盖
    for(auto t : opm) ins[t.tl].push_back(t), del[t.tr].push_back(t);
    for(auto t : qrym) qry[t.t].push_back(t);
    T1.build(l, r, 1); T2.build(l, r, 1);
    For(i, 1, tot){
        for(auto t : ins[i]){
            sl[t.l].insert(t.r), T1.update(t.l, l, r, 1);
            sr[t.r].insert(t.l); T2.update(t.r, l, r, 1);
        }
        for(auto t : qry[i]){
            int res = T1.find(t.l, mid, t.r, l, r, 1);
            covl[t.id] = res == -1 ? mid + 1 : res;
            res = T2.find(mid + 1, t.r, t.l, l, r, 1);
            covr[t.id] = res == -1 ? mid : res;
        }
        for(auto t : del[i]){
            sl[t.l].erase(sl[t.l].find(t.r)); T1.update(t.l, l, r, 1);
            sr[t.r].erase(sr[t.r].find(t.l)); T2.update(t.r, l, r, 1);
        }
    }
    For(i, 1, tot) ins[i].clear(), del[i].clear(), qry[i].clear();
    For(i, l, r) sl[i].clear(), sr[i].clear();
    //左区间覆盖
    for(auto t : opl) chg[t.l].push_back(t);
    for(auto t : qrym) qry[t.l].push_back(t), tor[t.id] = mid + 1;
    T3.build(1, tot, 1);
    For(i, l, mid){
        for(auto t : qry[i]) T3.update(t.t, {i, t.id}, 1, tot, 1);
        for(auto t : chg[i]) T3.modify(t.tl, t.tr, t.r + 1, 1, tot, 1);
        while(T3.mn[1][0] == i){
            int p = T3.mn[1][1]; tor[p] = i;
            T3.update(tim[p], {inf, 0}, 1, tot, 1);
        }
    }
    For(i, l, r) chg[i].clear(), qry[i].clear();
    //右区间覆盖
    for(auto t : opr) chg[t.r].push_back(t);
    for(auto t : qrym) qry[t.r].push_back(t), tol[t.id] = mid;
    T4.build(1, tot, 1);
    Rof(i, r, mid + 1){
        for(auto t : qry[i]) T4.update(t.t, {i, t.id}, 1, tot, 1);
        for(auto t : chg[i]) T4.modify(t.tl, t.tr, t.l - 1, 1, tot, 1);
        while(T4.mx[1][0] == i){
            int p = T4.mx[1][1]; tol[p] = i;
            T4.update(tim[p], {0, 0}, 1, tot, 1);
        }
    }
    For(i, l, r) chg[i].clear(), qry[i].clear();
    //统计答案，递归
    for(auto t : qrym) ans[t.id] = (tor[t.id] >= covl[t.id]) && (tol[t.id] <= covr[t.id]);
    solve(l, mid, dwnl, qryl); solve(mid + 1, r, dwnr, qryr);
}
void Solve(){
    cin >> n >> m;
    vector<int> v1, v2;
    For(i, 1, m){
        int op, t; cin >> op;
        if(op == 1){
            cin >> a[i].l >> a[i].r; --a[i].r;
            a[i].tl = i; a[i].tr = m; v1.push_back(i);
            if(a[i].l == a[i].r) tag[a[i].l]++;
        }
        else if(op == 2){
            cin >> t, a[t].tr = i - 1;
            if(a[t].l == a[t].r) tag[a[t].l]--;
        }
        else{
            cin >> b[i].l >> b[i].r; --b[i].r;
            b[i].id = ++q; b[i].t = i; v2.push_back(i);
            if(b[i].l == b[i].r) ans[q] = !!tag[b[i].l];
        }
    }
    vector<oper> all1; vector<que> all2;
    for(int i : v1) all1.push_back(a[i]);
    for(int i : v2) all2.push_back(b[i]);
    solve(1, n - 1, all1, all2);
    For(i, 1, q) cout << (ans[i] ? 'Y' : 'N') << '\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1; //cin >> T;
    while(T--) Solve();
    return 0;
}

如你所见，虽然我写了整整 7.6k，但是四棵线段树里前两棵和后两棵功能基本完全一致，而且剩下的地方也没什么繁琐的细节，所以其实好写好调。