Codeforces 1080F - Katya and Segments Sets - 可持久化线段树

Codeforces 1080F - Katya and Segments Sets - 可持久化线段树

题解链接

https://lucien.ink

题目链接

https://codeforces.com/contest/1080/problem/F

题目

It is a very important day for Katya. She has a test in a programming class. As always, she was given an interesting problem that she solved very fast. Can you solve that problem?

You are given $n$ ordered segments sets. Each segment can be represented as a pair of two integers $[l,r]$ where $l\le r$. Each set can contain an arbitrary number of segments (even $0$). It is possible that some segments are equal.

You are also given $m$ queries, each of them can be represented as four numbers: $a,b,x,y$. For each segment, find out whether it is true that each set $p$ ($a\le p\le b$) contains at least one segment $[l,r]$ that lies entirely on the segment $[x,y]$, that is $x\le l\le r\le y$.

Find out the answer to each query.

Note that you need to solve this problem online. That is, you will get a new query only after you print the answer for the previous query.

题意

  你有 $n$ 个集合，$k$ 条线段，每条线段都只属于一个集合，集合的编号为 $1\dots n$，允许存集合为空（为了叙述方便，在这里我们将编号为 $i$ 的集合中的第 $j$ 条线段简记为 $seg[i][j]$）。有 $m$ 次询问，每次询问有四个值 a b x y，问：

• $\forall i\in [a,b]$
• $\exists j$，使得 $seg[i][j]\subseteq segnment[x,y]$

  是否成立。

思路

  先从忽略时间、空间复杂度的角度去考虑问题。

  对于单个集合，考虑如何快速的求解答案。我们可以借助动态规划的思想，处理出左端点坐标大于等于 $x$ 的所有线段的右端点的最小值 $f[x]$，这样对于单次询问 x y，只需要判断 $f[x]\le y$ 是否成立即可。

  对于多个集合，我们将每个集合的 $f$ 函数都预处理出来，记 $f[i][x]$ 为编号为 $i$ 的集合中左端点坐标大于等于 $x$ 的所有线段的右端点的最小值，对于单次询问 a b x y，我们只需要判断 m a x { f [ a ] [ x ] , f [ a + 1 ] [ x ] … f [ b ] [ x ] } ≤ y max\{f[a][x], f[a + 1][x] \dots f[b][x]\} \leq y max{f[a][x],f[a+1][x]…f[b][x]}≤y 是否成立即可。

  这样一来，我们就从逻辑上得出了一种看似可行的做法，开始考虑优化。

  对于单次询问 a b x y，我们判断 m a x { f [ a ] [ x ] , f [ a + 1 ] [ x ] … f [ b ] [ x ] } ≤ y max\{f[a][x], f[a + 1][x] \dots f[b][x]\} \leq y max{f[a][x],f[a+1][x]…f[b][x]}≤y 是否成立时，可以观察到， m a x { f [ a ] [ x ] … f [ b ] [ x ] } max\{f[a][x] \dots f[b][x]\} max{f[a][x]…f[b][x]} 可以通过维护一颗叶节点 $i$ 代表 $f[i][x]$ 的最大值线段树来在 $O(lo{g}_2(n))$ 的时间内得到，可每次询问的时候，我都需要将线段树先清空，再将所有涉及到询问的集合中左端点的坐标大于等于 $x$ 的线段都一一重新插入，此时单次询问的复杂度为$O(n\cdot lo{g}_2(n))$。

  优化重构问题，显然需要用到可持久化数据结构，也就是可持久化线段树了。

  我们将所有线段都按左端点进行一次从大到小的 $sort$，右端点可以忽略，我们按照左端点从大到小的顺序将右端点插到可持久化线段树中，这样一来我们对某个拷贝进行查询的时候，就可以得到 m a x { f [ a ] [ x ] … f [ b ] [ x ] } max\{f[a][x] \dots f[b][x]\} max{f[a][x]…f[b][x]} 的值了，将其与 $y$ 作比较即可。单次询问复杂度为$O(lo{g}_2(n))$。

实现

https://pasteme.cn/2341

#include <bits/stdc++.h>
const int maxn = int(1e5) + 7, inf = 0x3f3f3f3f;
int n, m, k, key[maxn << 2], value[maxn << 2], len;
struct SegmentTree {
    struct Node {
        int val, l, r;
        Node():val(inf), l(0), r(0) {}
    } node[maxn << 6];
    int root[maxn << 2], size, cnt;
    SegmentTree():size(0), cnt(0) {}
    void pushup(int cur) {
        node[cur].val = std::max(node[node[cur].l].val, node[node[cur].r].val);
    }
    void update(int pos, int val, int &cur, int pre, int l, int r) {
        node[cur = ++size] = node[pre];
        if (l == r) {
            node[cur].val = std::min(node[cur].val, val);
            return ;
        }
        int mid = l + r >> 1;
        if (pos <= mid) update(pos, val, node[cur].l, node[pre].l, l, mid);
        else update(pos, val, node[cur].r, node[pre].r, mid + 1, r);
        pushup(cur);
    }
    int query(int ql, int qr, int cur, int l, int r) {
        if (cur == 0) return inf;
        if (ql <= l && r <= qr) return node[cur].val;
        int mid = l + r >> 1, ret = 0;
        if (ql <= mid) ret = std::max(ret, query(ql, qr, node[cur].l, l, mid));
        if (qr > mid) ret = std::max(ret, query(ql, qr, node[cur].r, mid + 1, r));
        return ret ? ret : inf;
    }
    void update(int pos, int val) {
        ++cnt;
        update(pos, val, root[cnt], root[cnt - 1], 1, n);
    }
    int query(int l, int r, int cur) {
        return query(l, r, root[cur], 1, n);
    }
} htj;
struct Segment { int l, r, p; } segment[maxn << 2];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++) scanf("%d%d%d", &segment[i].l, &segment[i].r, &segment[i].p);
    std::sort(segment + 1, segment + 1 + k, [](Segment x, Segment y) { return x.l == y.l ? x.r > y.r : x.l > y.l; });
    for (int i = 1; i <= k; i++) {
        if (segment[i].l != segment[i - 1].l) key[++len] = segment[i].l;
        value[len] = i;
        htj.update(segment[i].p, segment[i].r);
    }
    for (int i = 1, a, b, x, y; i <= m; i++) {
        scanf("%d%d%d%d", &a, &b, &x, &y);
        int pos = value[int(std::upper_bound(key + 1, key + 1 + len, x, std::greater<int>()) - key) - 1];
        puts(htj.query(a, b, pos) <= y ? "yes" : "no");
        fflush(stdout);
    }
    return 0;
}