一个显然的做法是二分答案后转化为查询区间颜色数，可持久化线段树记录每个位置上一个同色位置，离线后set+树状数组套线段树维护。这样是三个log的。
注意到我们要知道的其实只是是否所有颜色都在该区间出现，可以改为查询后缀区间的上一个同色位置中最小的。这样我们就只需要set+线段树就可以维护了，同样二分答案是两个log。直接在线段树上二分就变成了一个log。
给每种颜色在坐标-inf和inf处加点来避免乱七八糟的讨论。离散化一下。对于相同坐标的点，在叶子维护堆即可。调过样例就能1A了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<set> #include<queue> #include<vector> using namespace std; #define ll long long #define N 600010 #define inf 600000003 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,q,t,L[N<<2],R[N<<2],tree[N<<2],ans[N],u[N]; struct data { int x,t,op;int p,i; bool operator <(const data&a) const { return t<a.t||t==a.t&&abs(op)>abs(a.op); } }a[N<<2]; priority_queue<int,vector<int>,greater<int> > ins[N<<2],del[N<<2]; multiset<int> color[N]; void build(int k,int l,int r) { L[k]=l,R[k]=r;tree[k]=inf; if (l==r) return; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } int query(int k,int l,int r,int x,int last) { if (L[k]==R[k]) return max(u[L[k]]-x,x-last); int mid=L[k]+R[k]>>1; if (r<=mid) return query(k<<1,l,r,x,min(tree[k<<1|1],last)); else if (l>mid) return query(k<<1|1,l,r,x,last); else { if (u[mid]-x>x-min(last,tree[k<<1|1])) return query(k<<1,l,mid,x,min(last,tree[k<<1|1])); else return min(x-min(last,tree[k<<1|1]),query(k<<1|1,mid+1,r,x,last)); } } void modify(int k,int p,int x,int op) { if (L[k]==R[k]) { if (op==1) ins[k].push(x);else del[k].push(x); while (!del[k].empty()&&ins[k].top()==del[k].top()) ins[k].pop(),del[k].pop(); tree[k]=ins[k].empty()?inf:ins[k].top(); return; } int mid=L[k]+R[k]>>1; if (p<=mid) modify(k<<1,p,x,op); else modify(k<<1|1,p,x,op); tree[k]=min(tree[k<<1],tree[k<<1|1]); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj5462.in","r",stdin); freopen("bzoj5462.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(),q=read(); for (int i=1;i<=n;i++) { int x=read(),y=read(),l=read(),r=read(); t++;a[t].x=x,a[t].t=l,a[t].op=1,a[t].p=y; t++;a[t].x=x,a[t].t=r+1,a[t].op=-1,a[t].p=y; u[i]=x; } for (int i=1;i<=q;i++) t++,a[t].x=read(),a[t].t=read(),a[t].op=0,a[t].p=0,a[t].i=i,u[n+i]=a[t].x; sort(u+1,u+n+q+1);int v=unique(u+1,u+n+q+1)-u-1;u[0]=-inf,u[++v]=inf; for (int i=1;i<=t;i++) a[i].x=lower_bound(u,u+v+1,a[i].x)-u; build(1,0,v); sort(a+1,a+t+1); //for (int i=1;i<=t;i++) cout<<a[i].x<<' '<<a[i].t<<' '<<a[i].op<<' '<<a[i].p<<' '<<a[i].i<<endl; for (int i=1;i<=m;i++) { color[i].insert(0),color[i].insert(v); modify(1,v,-inf,1); } for (int i=1;i<=t;i++) if (a[i].op==0) ans[a[i].i]=query(1,a[i].x,v,u[a[i].x],inf); else if (a[i].op==-1) { multiset<int>::iterator it=color[a[i].p].find(a[i].x); it++;int x=*it; it--,it--;int y=*it; it++;color[a[i].p].erase(it); modify(1,x,u[a[i].x],-1),modify(1,a[i].x,u[y],-1),modify(1,x,u[y],1); } else { multiset<int>::iterator it=color[a[i].p].lower_bound(a[i].x); int x=*it; it--;int y=*it; color[a[i].p].insert(a[i].x); modify(1,x,u[a[i].x],1),modify(1,a[i].x,u[y],1),modify(1,x,u[y],-1); } for (int i=1;i<=q;i++) printf("%d ",ans[i]>inf/3?-1:ans[i]); return 0; }