传送门
首先二分答案 (mid)，问题变成求区间 ([l-mid,r+mid]) 在该年份的不同类型个数为 (k)
关于年份的限制可以离线下来
现在的问题就是区间数颜色，一个套路就是维护每个颜色的后继，即这个位置颜色的下一个位置
那么，如果有 ((-infty,l-mid-1]) 的某一个值大于 (r+mid) 就不合法
这个可以在线段树上二分实现
时间复杂度 (nlogn)
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO {
const int maxn(1 << 21 | 1);
char obuf[maxn], ibuf[maxn], *iS, *iT, c, *oS = obuf, *oT = obuf + maxn - 1, st[60];
int f, tp;
inline char Getc() {
return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++;
}
template <class Int> inline void In(Int &x) {
for (c = Getc(), f = 1; c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;
for (x = 0; c >= '0' && c <= '9'; c = Getc()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
inline void Flush() {
fwrite(obuf, 1, oS - obuf, stdout);
oS = obuf;
}
inline void Putc(char c) {
*oS++ = c;
if (oS == oT) Flush();
}
template <class Int> inline void Out(Int x) {
if (x < 0) Putc('-'), x = -x;
if (!x) Putc('0');
while (x) st[++tp] = x % 10 + '0', x /= 10;
while (tp) Putc(st[tp--]);
}
}
using IO :: In;
using IO :: Out;
using IO :: Putc;
using IO :: Flush;
const int maxn(3e5 + 5);
const int inf(1e9);
int n, q, k, rt, tot, type, vis[maxn], ans[maxn];
multiset <int> pos[maxn], heap[maxn * 20];
multiset <int> :: iterator it, ot, at;
struct Segment {
int ls, rs, mx, vmx;
} tr[maxn * 20];
struct Store {
int tp, x, tim, op;
inline bool operator <(Store b) const {
return tim < b.tim;
}
} str[maxn << 1];
struct Qry {
int x, tim, id;
inline bool operator <(Qry b) const {
return tim < b.tim;
}
} qry[maxn];
void Modify(int &x, int l, int r, int p, int v, int op) {
int mid;
if (!x) x = ++tot;
if (l == r) {
if (op == 1) heap[x].insert(v);
else heap[x].erase(heap[x].find(v));
at = heap[x].end();
tr[x].mx = heap[x].size() ? (*--at) : -inf;
tr[x].vmx = tr[x].mx + l;
return;
}
mid = (l + r) % 2 == 0 ? (l + r) / 2 : (l + r - 1) / 2;
p <= mid ? Modify(tr[x].ls, l, mid, p, v, op) : Modify(tr[x].rs, mid + 1, r, p, v, op);
tr[x].mx = max(tr[tr[x].ls].mx, tr[tr[x].rs].mx);
tr[x].vmx = max(tr[tr[x].ls].vmx, tr[x].mx + r);
}
int Query(int x, int l, int r, int ql, int qr) {
int mid, ret;
if (ql > qr) return inf;
if (!x || (ql <= l && qr >= r)) return tr[x].mx;
ret = -inf, mid = (l + r) >> 1;
if (ql <= mid) ret = Query(tr[x].ls, l, mid, ql, qr);
if (qr > mid) ret = max(ret, Query(tr[x].rs, mid + 1, r, ql, qr));
return ret;
}
int main() {
freopen("a.in", "r", stdin);
int cnt, i, j, x, t, a, b, mx, l, r, mid, cur, nmx, tmp, vmx;
In(n), In(k), In(q), cnt = mx = 0;
for (i = 1; i <= n; ++i) {
In(x), In(t), In(a), In(b);
str[++cnt] = (Store){t, x, a, 1};
str[++cnt] = (Store){t, x, b + 1, -1};
mx = max(mx, x);
}
sort(str + 1, str + cnt + 1);
for (i = 1; i <= q; ++i) {
In(qry[i].x), In(qry[i].tim);
qry[i].id = i, mx = max(mx, qry[i].x);
}
sort(qry + 1, qry + q + 1), tr[0].vmx = tr[0].mx = -inf;
for (i = 1; i <= k; ++i) pos[i].insert(-mx), pos[i].insert(inf), Modify(rt, -mx, mx, -mx, inf, 1);
for (i = 1, j = 1; i <= q; ++i) {
while (j <= cnt && str[j].tim <= qry[i].tim) {
if (str[j].op == 1) {
type += (vis[str[j].tp] == 0), ++vis[str[j].tp];
ot = it = pos[str[j].tp].insert(str[j].x);
--it, ++ot;
Modify(rt, -mx, mx, *it, *ot, -1);
Modify(rt, -mx, mx, *it, str[j].x, 1);
Modify(rt, -mx, mx, str[j].x, *ot, 1);
}
else {
type -= (vis[str[j].tp] == 1), --vis[str[j].tp];
ot = it = pos[str[j].tp].find(str[j].x);
--it, ++ot;
Modify(rt, -mx, mx, *it, *ot, 1);
Modify(rt, -mx, mx, *it, str[j].x, -1);
Modify(rt, -mx, mx, str[j].x, *ot, -1), ++it, pos[str[j].tp].erase(it);
}
++j;
}
if (type != k) ans[qry[i].id] = -1;
else {
l = -mx, r = mx, cur = rt, vmx = nmx = -inf;
while (l < r) {
mid = (l + r) >> 1;
tmp = max(nmx + mid, tr[tr[cur].ls].vmx);
if (tmp >= qry[i].x + qry[i].x || qry[i].x <= mid + 1) cur = tr[cur].ls, r = mid;
else vmx = tmp, nmx = max(nmx, tr[tr[cur].ls].mx), cur = tr[cur].rs, l = mid + 1;
}
if (Query(rt, -mx, mx, -mx, l) + l >= qry[i].x + qry[i].x) --l;
ans[qry[i].id] = qry[i].x - l - 1;
}
}
for (i = 1; i <= q; ++i) Out(ans[i]), Putc('
');
return Flush(), 0;
}