lg4169 发表于 2019-10-12 | 分类于 算法 | 阅读数 次 链接:lg4169 题解当满足的点在询问点左下角时去掉绝对值,转换为三维偏序问题,坐标翻转即可将另三个区域的点转换为左下角的点 或4次cdq采用不同的树状数组最后取最值 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include<bits/stdc++.h>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define lowbit(x) x&(-x)using namespace std;const int INF=0x3f3f3f3f;const int N=1e6+7;struct node{ int x,y,t,key,op;}p[N],t[N],a[N];int tr[N];int n,m,mx,my;inline void update(int x,int y){for(;x<=my;x+=lowbit(x))tr[x]=max(tr[x],y);}inline int query(int x){int res=-1;for(;x;x-=lowbit(x))res=max(res,tr[x]);return res;}inline int cmpx(node x,node y){return x.x==y.x?x.y<y.y:x.x<y.x;}void cdq(int l,int r){ if(l==r)return ; int mid=l+r>>1; cdq(l,mid);cdq(mid+1,r); int posa=l,posb=mid+1; while(posb<=r){ while(posa<=mid&&a[posa].x<=a[posb].x){ if(a[posa].op==1)update(a[posa].y,a[posa].x+a[posa].y); ++posa; } if(a[posb].op==0){ int tp=query(a[posb].y); if(tp)p[a[posb].t].key=min(p[a[posb].t].key,a[posb].x+a[posb].y-tp); } ++posb; } rep(i,l,posa-1)if(a[i].op==1)for(int j=a[i].y;j<=my;j+=lowbit(j))tr[j]=0; //sort(a+l,a+r+1,cmpx); int i=l,j=mid+1,k=l-1; while(j<=r){ while(i<=mid&&cmpx(a[i],a[j]))t[++k]=a[i++]; t[++k]=a[j++]; } while(j<=r)t[++k]=a[j++]; while(i<=mid)t[++k]=a[i++]; rep(i,l,r)a[i]=t[i];}inline void init(){ rep(i,1,n)a[i]=p[i];}int main(){ scanf("%d%d",&n,&m); rep(i,1,n){ int x,y; scanf("%d%d",&x,&y); x++,y++; p[i]=node{x,y,i,x+y,1}; mx=max(x,mx); my=max(y,my); } while(m--){ int op,x,y; scanf("%d%d%d",&op,&x,&y); x++,y++; if(op==1)p[++n]=node{x,y,n,x+y,1}; else p[++n]=node{x,y,n,INF,0}; mx=max(x,mx); my=max(y,my); } init(); cdq(1,n); rep(i,1,n)p[i].x=mx-p[i].x+1; init(); cdq(1,n); rep(i,1,n)p[i].y=my-p[i].y+1; init(); cdq(1,n); rep(i,1,n)p[i].x=mx-p[i].x+1; init(); cdq(1,n); rep(i,1,n)if(p[i].op==0)printf("%d\n",p[i].key); return 0;}