点此看题
不难发现答案具有单调性，所以对于每个询问都可以二分答案。
具体来说对于位置 x x x，如果答案 ≥ m \geq m ≥m，那么等价于存在一种店在 ( x − m , x + m ) (x-m,x+m) (x−m,x+m)不存在店，但是区间并不好维护，可以使用前驱来判断存在与否，那么等价于在 [ x + m , i n f ) [x+m,inf) [x+m,inf)存在店的前驱 ≤ x − m \leq x-m ≤x−m，那么我们只需要判断 [ x + m , i n f ) [x+m,inf) [x+m,inf)前驱的最小值 m n ≤ x − m mn\leq x-m mn≤x−m
每个位置的前驱，用线段树来维护即可，一开始可以把所有用到的位置离散化，然后对于每种店都维护一个 s e t \tt set set来算前驱，先要插入 − i n f -inf −inf和 i n f inf inf。每一个位置用 s e t \tt set set维护前驱（位置要先离散化），那么一开始位置 i n f inf inf的前驱就有 k k k个 − i n f -inf −inf，我们要有所有的店种才能去掉这个 − i n f -inf −inf，所以判断位置 i n f inf inf是否有 − i n f -inf −inf就可以知道是否所有店种齐备。
二分可以在线段树上实现，我们二分 x + m x+m x+m为 i i i，那么 m n + i ≤ 2 x mn+i\leq 2x mn+i≤2x，我们要明确 i i i越小那么 m n mn mn也越小，他们两个都是单调的。如果左边的最大位置 < x <x <x那么只能往右边分，否则我们判断 m i d + 1 mid+1 mid+1（ m i d mid mid指中间的位置）能不能满足条件，如果满足我们往右边分；不满足往左边分，还要用右边的前驱更新 m n mn mn，到了最底层的位置也就知道答案了。
需要注意 m u l t i s e t \tt multiset multiset的使用方法，删除一个元素只能删指针，删值会把相等的所有值都删去。
#include <cstdio> #include <algorithm> #include <cstring> #include <set> using namespace std; #define point multiset<int>::iterator const int M = 300005; const int inf = 1e8+100; int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int n,m,N,k,d,a[M],ans[M],mn[4*M],mx[4*M]; struct node { int x,t,a; bool operator < (const node &b) { return a<b.a; } }qa[M],qb[M],q[M]; multiset<int> s[M],p[M]; void lisan() { sort(a+1,a+1+n); n=unique(a+1,a+1+n)-a;//n+1¸öµã for(d=1;d<n;d*=2);d--; for(int i=1;i<=1200000;i++) mn[i]=inf; for(int i=1;i<=k;i++) p[n].insert(-inf); for(int i=1;i<=n;i++) p[i].insert(inf); for(int i=d+n;i;i>>=1) mn[i]=-inf; for(int i=1;i<n;i++) mx[i+d]=a[i]; mx[n+d]=2*inf; for(int i=d;i>=1;i--) mx[i]=max(mx[i<<1],mx[i<<1|1]); } void upd(int i) { mn[i+d]=(*p[i].begin()); i+=d; while(i>>=1) { mn[i]=min(mn[i<<1],mn[i<<1|1]); } } int ask(int x) { if(mn[n+d]==-inf) return -1; int i=1,mi=inf; while(i<=d) { if(mx[2*i]<x) {i=2*i+1;continue;} if(mx[2*i]+1+min(mi,mn[2*i+1])<=2*x) i=2*i+1; else { mi=min(mi,mn[2*i+1]); i=2*i; } } return min(x-min(mi,mn[i]),mx[i]-x); } void Add(int i,int x) { p[i].insert(x); upd(i); } void Del(int i,int x) { point it=p[i].find(x); p[i].erase(it); upd(i); } int get(int x) { return lower_bound(a+1,a+n,x)-a; } void add(int i,int x) { point it1=s[i].insert(x),it2=it1; it1--;it2++; Add(get(x),*it1); Del(get(*it2),*it1);Add(get(*it2),x); } void del(int i,int x) { point it=s[i].find(x),it1=it,it2=it1; it1--;it2++; Del(get(x),*it1); Del(get(*it2),x);Add(get(*it2),*it1); s[i].erase(it);//multiset can only delete the point! Attention! } signed main() { N=n=read();k=read();m=read(); for(int i=1;i<=n;i++) { int x=read(),t=read(),l=read(),r=read(); qa[i]=node{x,t,l}; qb[i]=node{x,t,r}; a[i]=x; } lisan(); for(int i=1;i<=m;i++) { int l=read(),y=read(); q[i]=node{l,i,y}; } sort(qa+1,qa+1+N); sort(qb+1,qb+1+N); sort(q+1,q+1+m); for(int i=1;i<=k;i++) s[i].insert(inf),s[i].insert(-inf); for(int i=1,ja=1,jb=1;i<=m;i++) { while(ja<=N && qa[ja].a<=q[i].a) add(qa[ja].t,qa[ja].x),ja++; while(jb<=N && qb[jb].a<q[i].a) del(qb[jb].t,qb[jb].x),jb++; ans[q[i].t]=ask(q[i].x); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); }