码力底下，思维迟钝，我该怎么办？

还是说这题太毒？

题意

给定一个 \(n\) 个商店，第 \(i\) 个商店的类型为 \(t_i\)，在 \([a_i, b_i]\) 时间营业，位于位置 \(x_i\)。

定义某一时刻一种商店到某一个位置的距离为：该时刻营业的所有该种商店中到该位置的距离的最小值。

现在给定 \(q\) 个询问，每次询问在时刻 \(y_i\) 询问所有类型的商店到位置 \(x_i\) 的距离最大值。

\(1 \leq n, q \leq 3 \times 10^5\)

思路

线段树 + set 维护。

首先考虑对题目给出的位置和时间进行离散化。

然后可以考虑按照时间顺序维护操作，变成一个动态的维护问题。

拆一下操作，等价于维护：

1. 在某一时刻，在某一位置插入一个商店

2. 同 1，但删除商店

3. 询问

询问显然具有单调性，所以可以考虑二分。

假设当前二分出的区间是 \([l, r]\)，二分的判定问题是：判断 \([l, r]\) 中是否出现过所有颜色。

区间数颜色做法显然可以做，但是复杂度是假的。

我们发现只需要判断所有颜色是否都出现过，因此考虑更简单的做法。

令 \(nxt(r, c)\) 表示在位置 \(r\)，类型为 \(c\) 的商店的后继，一种颜色在区间 \([l, r]\) 中出现过的充要条件是：\([1, l)\) 中所有位置的 \(nxt\) 不超过 \(r\).

那么对于多种颜色，只需要上线段树维护前缀 \(nxt\) 的最大值。

但是这题恶心的地方在于可能有多个商店在同一个位置。现在的问题是：插入和修改的操作应该怎么对应修改 \(nxt\)？

考虑维护类似链表的结构。不妨用一个 multiset 来维护 \(nxt\)，当第一次插入某个 \(nxt\) 或删除完所有的 \(nxt\)，就将对应位置的 \(nxt\) 集合相应地修改，\(nxt\) 集合的最值变化说明需要相应地修改线段树。

为了躲边界问题，可以先在序列开头加入所有类型的商店，并且在左右两端加两个边界端点。

注意离散化之后要相应地二分算距离。

代码

#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

const int maxn = 3e5 + 5;
const int maxq = 3e5 + 5;
const int sgt_sz = maxn << 2;

struct Query
{
    int x, c, t, p;
} opt[maxn * 3];

int n, k, q, m;
int len;
int ans[maxq];
int pos[maxn], sa[maxn];
int val[sgt_sz];
multiset<int, greater<int> > s[maxn];
map<int, int> cnt[maxn];

inline int read()
{
    int res = 0, flag = 1;
    char ch = getchar();
    while ((ch < '0') || (ch > '9'))
    {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while ((ch >= '0') && (ch <= '9'))
    {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res * flag;
}

inline void write(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

void push_up(int k) { val[k] = max(val[k << 1], val[k << 1 | 1]); }

void update(int k, int l, int r, int p, int w)
{
    if (l == r)
    {
        val[k] = w;
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) update(k << 1, l, mid, p, w);
    else update(k << 1 | 1, mid + 1, r, p, w);
    push_up(k);
}

int query(int k, int l, int r, int p)
{
    if (r <= p) return val[k];
    int mid = (l + r) >> 1, res = 0;
    res = max(res, query(k << 1, l, mid, p));
    if (mid < p) res = max(res, query(k << 1 | 1, mid + 1, r, p));
    return res;
}

bool cmp(const Query& a, const Query& b) { return (a.t != b.t ? a.t < b.t : a.p < b.p); }

void _add(int x, int c)
{
    s[x].insert(c);
    if (c > sa[x]) sa[x] = c, update(1, 1, m, x, c);
}

void _del(int x, int c)
{
    s[x].erase(s[x].find(c));
    int curc = (*s[x].begin());
    if (curc < sa[x]) sa[x] = curc, update(1, 1, m, x, curc); 
}

void add(int x, int c)
{
    if (cnt[c].count(x)) { cnt[c][x]++; return; }
    auto it = cnt[c].upper_bound(x);
    int r = it -> first, l = (--it) -> first;
    _del(l, r), _add(x, r), _add(l, x);
    cnt[c].insert(make_pair(x, 1));
}

void del(int x, int c)
{
    if (cnt[c].count(x) && (cnt[c][x] > 1)) { cnt[c][x]--; return; }
    cnt[c].erase(x);
    auto it = cnt[c].upper_bound(x);
    int r = it -> first, l = (--it) -> first;
    _del(x, r), _del(l, x), _add(l, r);
}

void qry(int x, int p)
{
    int l = 0, r = 1e8 + 50;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        int top = lower_bound(pos + 1, pos + m + 1, x - mid) - pos - 1;
        // printf("debug %d %d %d\n", x, mid, top);
        if (pos[query(1, 1, m, top)] <= x + mid) r = mid;
        else l = mid + 1;
    }
    // printf("debug %d\n", l);
    ans[p] = l;
}

int main()
{
    n = read(), k = read(), q = read();
    for (int i = 1, c; i <= n; i++)
    {
        pos[i] = read(), c = read();
        opt[++len] = (Query){pos[i], c, read(), 0};
        opt[++len] = (Query){pos[i], c, read() + 1, -1};
    }
    pos[n + 1] = -5e8, pos[n + 2] = 5e8;
    sort(pos + 1, pos + n + 3);
    m = unique(pos + 1, pos + n + 3) - pos - 1;
    for (int i = 1; i <= m; i++) s[i].insert(0);
    for (int i = 1; i <= k; i++)
    {
        cnt[i].insert(make_pair(1, 1));
        cnt[i].insert(make_pair(m, 1));
        s[1].insert(m);
    }
    sa[1] = m;
    update(1, 1, m, 1, m);
    for (int i = 1; i <= len; i++) opt[i].x = lower_bound(pos + 1, pos + m + 1, opt[i].x) - pos;
    for (int i = 1, x, t; i <= q; i++)
    {
        x = read(), t = read();
        opt[++len] = (Query){x, 0, t, i};
    }
    sort(opt + 1, opt + len + 1, cmp);
    for (int i = 1; i <= len; i++)
        if (opt[i].p == 0) add(opt[i].x, opt[i].c);
        else if (opt[i].p == -1) del(opt[i].x, opt[i].c);
        else qry(opt[i].x, opt[i].p);
    for (int i = 1; i <= q; i++) write(ans[i] > 1e8 ? -1 : ans[i]), putchar('\n');
    return 0;
}