P8473题解

· · 题解

写在前面

提供一种在线做法。

这本来是一道绿题，但是我考试的时候脑抽了，一度认为是紫题往上，因为我熟悉的线段树 fail 了我 ಥ_ಥ。后来一看才发现是忘了每次都输出了，考试完恍然大悟，一交就过了，所以还是写一下，毕竟折磨了我一个多小时。

前置知识

题目描述（戳这里查看原题）

数轴上有一些黑白点（特殊整点），定义两个操作：

  1. 将区间 [l,r] 中所有特殊整点两两组成的线段加入一个可重集合 S 中。
  2. 撤销某次操作。保证撤销的操作类型为 1。

每次操作后可以任意次将 S 中由两个黑色点组成的线段中间的所有点染黑。询问每次操作后是否可以将原数轴上所有点染黑？

正文

我这道题是一眼瞄出来的，因为昨天的 REOI 也考了一道线段树维护区间的题，所以有意往这方向想，不过我们还是仔细看看这题还有什么可以提示我们的。

题目里说各组询问互相独立，但其实模拟一下会发现只要顺着按最优方法模拟，询问间就不会有影响。可以在线。

分析

其实题目里说的很隐晦，似乎每次添加的线段很多，然而，真正有用的线段只和能否进行操作有关。因此，对询问和修改有用的线段只有两端都是黑点的线段。

再往深处想，对于每次操作 1，这段区间中最长的“两端黑线段”所起的作用一定能包括内部所有“两端黑线段”起的作用（大区间一定覆盖小区间）。因此，每次操作我们只用考虑一个实际线段。

对于一段区间中最长的“两端黑线段”，我们在添加这个线段后把其能覆盖的所有白色点全部变成黑色一定是最优的，不用受其他操作影响。这就指向了区间修改，我们也就可以考虑从线段树的角度入手这道题。

实现

首先来考虑区间维护。首先，整个数轴的范围是 10^9 级别的，肯定不行。而对我们有用的整数点在 5\times 10^5 级别内，因此我们线段树只维护这些整数点就可以。

询问的问题是所有整点有没有白色，因此查询线段树就查询线段里有没有白色就好。直接按题目输入定义。形象化一点，就像在大线段上下雪，一次“两端黑线段”操作就在对应的区间覆盖一层雪，初始时黑点下一层雪，白点没有。因此之后我们查找厚度即可，一层没有就是白点。（感觉撒煤粉更合理 doge）

我们定义一段线段的最小值 v：

这样定义其实也很方便操作。我们只需要记录一段区间的最小值，一次“两端黑线段”操作只需要区间加 1 就好。询问只用判断整个线段的最小值是不是 0 即可。

还有一个问题，就是如何找到操作区间 [l,r] 的最长“两端黑线段”？
我们通过 C ++ 内置函数解决。

最后的时间复杂度是 O(n\log n)。

一些细节

  1. 对于刚才那个问题，我们不能直接在 p 数组上操作，因为里面还有白色点位置，所以我们要另外开一个数组（注意保证单调性）。

  2. 我们需不需要考虑变成黑色点的白色点？

    其实不用。如下图：

    如果选定区间能包括从白色变成黑色的点，那一定有：

    • 不包括“两端黑线段”端点。则整个区间在这条线段里，一定都是黑的，没有操作必要，不用管。
    • 包括“两端黑线段”端点，则这个由白变黑的点到端点之间也一定全是黑点，因此操作时考虑变化点和直接考虑原来的黑点的效果是等价的。（当时我没想明白，一度认为是紫题）

  3. 如果我们在区间 [l,r] 里找不到两个黑点怎么办？

    其实这种情况就是一定没有能力使区间中的白点变黑的，具体证明可以联想 2。所以直接忽略就好。

    注意：一定要每次输出一次询问，不要一不合法就直接 continue;。

  4. 操作 2 如何处理？

    把每个操作 1 记录下来，每次删除时只需要找出操作 1 时覆盖的“两端黑线段”，“铲一层雪”就可以，也就是该区间整体 -1。

代码

变量名见注释。

#include <iostream>
#include <algorithm>
#include <cstring>

#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid ((l + r) >> 1)

using namespace std;
typedef pair<int, int> pii;
const int maxn = 500005;

int a[maxn], p[maxn];
int blk[maxn], len;//只记录黑点位置（black）
int id[maxn];//记录黑点编号对应原数轴的编号
int n, q;
pii opts[maxn]; //记录所有操作 1
struct SegmentTree{
    int mn;//区间最小值。用于找白点。
    int lazy;
}tr[maxn << 2];

void pushup(int id){
    tr[id].mn = min(tr[ls].mn, tr[rs].mn);
}

void build(int id, int l, int r){
    if (l == r){
        tr[id].mn = a[l];
        return;
    }
    build(ls, l, mid),
    build(rs, mid+1, r);
    pushup(id);
}

void pushdown(int id){
    if (tr[id].lazy){
        tr[ls].lazy += tr[id].lazy;
        tr[rs].lazy += tr[id].lazy;
        tr[ls].mn += tr[id].lazy;
        tr[rs].mn += tr[id].lazy;
        tr[id].lazy = 0;
    }
}

void update(int id, int l, int r, int a, int b, int v){
    if (a <= l && r <= b){
        tr[id].mn += v;
        tr[id].lazy += v;
        return;
    }
    pushdown(id);
    if (a <= mid) update(ls, l, mid, a, b, v);
    if (b > mid) update(rs, mid+1, r, a, b, v);
    pushup(id);
}

int query(int id, int l, int r, int a, int b){
    if (a <= l && r <= b){
        return tr[id].mn;
    }
    pushdown(id);
    int res = 1e9;
    if (a <= mid) res = min(res, query(ls, l, mid, a, b));
    if (b > mid) res = min(res, query(rs, mid+1, r, a, b));
    return res;
}

int findL(int x){//找最左的黑点
    return id[lower_bound(blk+1, blk+1+len, x)-blk];
}

int findR(int x){//找最右的黑点
    return id[upper_bound(blk+1, blk+1+len, x)-blk-1];
}

void check(){//每次的询问
    if (query(1, 1, n, 1, n) <= 0) cout << "No" << endl;
    else cout << "Yes" << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i ++){
        cin >> p[i];
    }
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
        if (a[i]){
            blk[++len] = p[i];
            id[len] = i;
        }
    }
    build(1, 1, n);

    for (int k = 1; k <= q; k ++){
        check();//注意！
        int op;
        cin >> op;
        if (op & 1){//1
            int L, R;
            cin >> L >> R;
            int l = findL(L), r = findR(R);
            if (l > r) continue;
            if (!l || !r) continue;
            update(1, 1, n, l, r, 1);
            opts[k] = make_pair(L, R);
        }
        else{//2
            int x;
            cin >> x;
            int l = findL(opts[x].first), r = findR(opts[x].second);
            if (l > r) continue;
            if (!l || !r) continue;
            update(1, 1, n, l, r, -1);
        }
    }
    check();//注意！

    return 0;
}

总结

以前错误的觉得想要提升就要练蓝紫题，本来这场 Div.3 都懒得参加，但是后来参加了才发现自己甚至还有许多基础没搞明白，所谓地基要牢固，多补习基础知识才是正道。

这道题中线段树的用法很经典，就是区间覆盖解决一些问题，推荐几个题目P8463 「REOI-1」深潜的第六兽、P1442 铁球落地。

谢谢观看！