题解
成功把自己写自闭了
离散化之后再二分我是真不会算坐标啊我这个zz
先离散化所有坐标，然后对于每个位置维护一个最小前驱，然后线段树区间维护最小前驱
什么？位置一样？那就给每个大小为1的位置开个multiset，往上维护的时候就直接左右区间取min
然后就是，在线段树上二分了
我们把正无穷和负无穷位置加进去会比较好维护
如果\((x - m,x + m)\)这个区间不合法，转化为\([x + m,+\infty)\)有前驱在\((-\infty,x - m]\)内
也就意味着我们的距离大小至少是m
在线段树上二分呢，我们找的是这个\(x + m\)在的区间，显然x在右区间就往右区间走
如果x在左区间，那么看看\(mid + 1\)所在的点算出的\(m = pos[mid + 1] - x\)是否满足最小前缀\(mn <= x - m\)
如果满足这个\(x + m\)肯定在右区间
不满足就在左区间
然而，当你二分到一个点的时候，事实上，这个\(x + m\)是可能落在两个坐标中间的，也就是当前节点和当前节点+1，分别计算输出即可
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,K,Q;
struct qry_node {
int y,x,t;
friend bool operator < (const qry_node &a,const qry_node &b) {
if(a.y != b.y) return a.y < b.y;
else if(a.t != b.t) return a.t > b.t;
return a.x < b.x;
}
}qry[MAXN * 4];
int qt;
int pos[MAXN],tot,ans[MAXN],cnt[MAXN],hs;
struct node {
int l,r,mq;
}tr[MAXN * 4];
multiset<int> S[MAXN];
multiset<int> T[MAXN * 4];
void update(int u) {
tr[u].mq = min(tr[u << 1].mq,tr[u << 1 | 1].mq);
}
void build(int u,int l,int r) {
tr[u].l = l;tr[u].r = r;
if(l == r) {
tr[u].mq = tot + 1;
if(l == tot) {
tr[u].mq = 1;
for(int i = 1 ; i <= K ; ++i) T[u].insert(1);
}
return;
}
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
update(u);
}
void Change(int u,int pos,int v) {
if(tr[u].l == tr[u].r) {
if(v > 0) T[u].insert(v);
else T[u].erase(T[u].find(-v));
if(T[u].size() >= 1) tr[u].mq = *T[u].begin();
else tr[u].mq = tot + 1;
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(pos <= mid) Change(u << 1,pos,v);
else Change(u << 1 | 1,pos,v);
update(u);
}
void Query(int u,int x,int suf,int &a) {
if(tr[u].l == tr[u].r) {
int t = min(tr[u].mq,suf);
a = max(a,min(x - pos[t],pos[tr[u].l] - x));
if(tr[u].l < tot) a = max(a,min(x - pos[suf],pos[tr[u].l + 1] - x));
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(x > pos[mid]) {return Query(u << 1 | 1,x,suf,a);}
else {
int t = min(tr[u << 1 | 1].mq,suf);
if(pos[t] > 2 * x - pos[mid + 1]) {
return Query(u << 1,x,min(suf,tr[u << 1 | 1].mq),a);
}
else if(pos[t] <= 2 * x - pos[mid + 1]) {return Query(u << 1 | 1,x,suf,a);}
}
}
void Init() {
read(N);read(K);read(Q);
int x,t,a,b;
for(int i = 1 ; i <= N ; ++i) {
read(x);read(t);read(a);read(b);
qry[++qt] = (qry_node){a,x,t};
qry[++qt] = (qry_node){b + 1,x,-t};
pos[++tot] = x;
}
int l,y;
for(int i = 1 ; i <= Q ; ++i) {
read(l);read(y);
qry[++qt] = (qry_node){y,l,- i - K};
//pos[++tot] = l;
}
pos[++tot] = -1e9;pos[++tot] = 2e9;
sort(qry + 1,qry + qt + 1);
sort(pos + 1,pos + tot + 1);
tot = unique(pos + 1,pos + tot + 1) - pos - 1;
build(1,1,tot);
}
void Solve() {
for(int i = 1 ; i <= K ; ++i) {
S[i].insert(1),S[i].insert(tot);
}
for(int i = 1 ; i <= qt ; ++i) {
int u = qry[i].t;
if(u >= -K) {
int x = lower_bound(pos + 1,pos + tot + 1,qry[i].x) - pos;
if(u > 0) {
S[u].insert(x);
auto k = S[u].find(x);
auto g = k,h = k;++g,--h;
if(*g != *k) {
Change(1,*g,*k);Change(1,*g,-(*h));
Change(1,*k,*h);
}
if(cnt[u] == 0 && cnt[u] + 1 == 1) ++hs;
++cnt[u];
}
else {
u = -u;
auto k = S[u].find(x);
auto g = k,h = k;++g,--h;
if(*g != *k) {
Change(1,*g,-(*k));Change(1,*g,*h);
Change(1,*k,-(*h));
}
S[u].erase(k);
if(cnt[u] == 1 && cnt[u] - 1 == 0) --hs;
--cnt[u];
}
}
else {
if(hs != K) ans[- K - u] = -1;
else Query(1,qry[i].x,tot + 1,ans[-K - u]);
}
}
for(int i = 1 ; i <= Q ; ++i) {
out(ans[i]);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}