题意
Sol
这题没有想象中的那么难，但也绝对不简单。
首先把所有的询问离线，按照出现的顺序。维护时间轴来处理每个询问
对于每个询问((x_i, y_i))，可以二分答案(mid)。
问题转化为对于所有(a_i leqslant y_i leqslant b_i)的商店，((x - mid, x + mid))内是否所有类型的商店都出现过
若都出现过，减小(mid)，否则增大(mid)
现在有两个问题：
-
如何维护当前可行的所有商店，以及我们需要的信息
-
如何判断((x - mid, x + mid))内是否所有类型的商店都出现过
显然问题1依赖于问题2
对于第二个问题，一种方法是直接树套树区间数颜色，另一个巧妙的方法是定义(pre_i)表示和(i)号位置类型相同的商店中，(x)坐标小于(i)的第一个位置
若(mid)是合法的，一定存在一个位置(p in (x + mid + 1, N))满足(pre_p < x - mid)
那么直接用线段树维护(pre)的最小值即可。
线段树应该动态开点，当然你也可以头铁写离散化然后就需要考虑各种边界问题。。
问题1实际上我们只需要维护好(pre)即可
一个显然的想法是直接开(30w)个set维护每个类型
加入 / 删除的时候只会影响到(3)个位置
时间复杂度：(O(nlog^2n))，单次询问的复杂度为(O(logn))
需要注意一个细节，由于是在线段树上二分，所以二分的边界应该与线段树相同
#include<bits/stdc++.h>
#define mit multiset<int>::iterator
using namespace std;
const int MAXN = 3e5 + 10, L = 1e9, Lim = (1 << 22) + 1;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, K, Q, cnt, rt, ans[MAXN];
multiset<int> op[MAXN];//val of each type
multiset<int> s[Lim];//
int Mn[Lim], ls[Lim], rs[Lim];
struct Query {
int ti, opt, x;// time type pos
bool operator < (const Query &rhs) const {
return ti == rhs.ti ? opt < rhs.opt : ti < rhs.ti;
}
}q[MAXN * 3 + 10];
int tot = 0;
void Erase(multiset<int> &s, int &val) {
mit t = s.find(val);
if(t != s.end()) s.erase(t);
}
void update(int k) {
Mn[k] = min(Mn[ls[k]], Mn[rs[k]]);
}
void Insert(int &k, int l, int r, int x, int New, int Old) {
if(!k) k = ++tot;
if(l == r) {
if(New) s[k].insert(New);
if(Old) Erase(s[k], Old);
Mn[k] = (s[k].empty() ? L : *s[k].begin()); return ;
}
int mid = l + r >> 1;
if(x <= mid) Insert(ls[k], l, mid, x, New, Old);
else Insert(rs[k], mid + 1, r, x, New, Old);
update(k);
}
int query(int x) {
int l = 0, r = L, mid, now = rt, lim = L, ans;
while(l < r) {
int mid = l + r >> 1, mn = min(Mn[rs[now]], lim);
if((x > mid) || (mid - x < x - mn))
l = mid + 1, now = rs[now], ans = mid;
else r = mid, now = ls[now], lim = mn;
}
return l - x;
}
N = read(); K = read(); Q = read(); Mn[0] = L;
for(int i = 1; i <= N; i++) {
int x = read(), t = read(), a = read(), b = read();
q[++cnt] = (Query) {a, t, x};
q[++cnt] = (Query) {b + 1, -t, x};
}
for(int i = 1; i <= Q; i++) {
int x = read(), y = read();
q[++cnt] = (Query) {y, N + i, x};
}
sort(q + 1, q + cnt + 1); int Now = 0;// now type num
for(int i = 1; i <= K; i++) op[i].insert(L), op[i].insert(-L), Insert(rt, 0, L, L, -L, 0);
for(int i = 1; i <= cnt; i++) {
int ty = q[i].opt;
if(ty > N)
ans[ty - N] = Now < K ? - 1 : query(q[i].x);
else if(ty > 0) { // add
mit t = op[ty].upper_bound(q[i].x), r = t--;
Insert(rt, 0, L, *r, q[i].x, *t);
Insert(rt, 0, L, q[i].x, *t, 0);
if(op[ty].size() == 2) Now++;
op[ty].insert(q[i].x);
} else {
ty = -ty;
mit t = op[ty].upper_bound(q[i].x), r = t--; t--;
Insert(rt, 0, L, *r, *t, q[i].x);
Insert(rt, 0, L, q[i].x, 0, *t);
Erase(op[ty], q[i].x);
if(op[ty].size() == 2) Now--;
}
}
for(int i = 1; i <= Q; i++) printf("%d
", ans[i]);
return 0;
}