BZOJ 2716

http://www.lydsy.com/JudgeOnline/problem.php?id=2716

x坐标排序

时间cdq分治

y坐标树状数组维护

对于每次询问左下角的点维护前缀最大值x+y

然后坐标翻转做剩下三次操作

#include
#include
#define gc getchar()
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using std::sort;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a=0?x:-x;}
const int N=1200011,M=4000011,inf=(1<<27);
int ans[N];
int n,m,maxx;
struct point{int x,y,t,k,pos;inline bool operator<(point A)const{if(x!=A.x)return x>1;int j=l,k=mid+1;FOR(i,l,r){if(p[i].k==1&&p[i].t<=mid)add(p[i].y,(p[i].x+p[i].y));if(p[i].k==2&&p[i].t>mid)ans[p[i].pos]=min(ans[p[i].pos],(p[i].x+p[i].y-query(p[i].y)));}FOR(i,l,r)if(p[i].k==1&&p[i].t<=mid)del(p[i].y);FOR(i,l,r)p[i].t<=mid?t[j++]=p[i]:t[k++]=p[i];FOR(i,l,r)p[i]=t[i];cdq(l,mid);cdq(mid+1,r);
}
inline int read(){char c;while(c=gc,c==' '||c=='\n');int data=c-48;while(c=gc,c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data;
}
int main(){n=read();m=read();FOR(i,1,n){p[i].t=i;p[i].k=1;p[i].x=read();p[i].y=read();maxx=max(maxx,max(abs(p[i].x),abs(p[i].y)));}FOR(i,(n+1),(n+m)){p[i].k=read();p[i].x=read();p[i].y=read();p[i].t=i;maxx=max(maxx,max(abs(p[i].x),abs(p[i].y)));if(p[i].k==2){ans[++ans[0]]=inf;p[i].pos=ans[0];}}n+=m;++maxx;FOR(i,1,n)p[i].x+=maxx,p[i].y+=maxx;maxx<<=1;FOR(i,0,maxx)tr[i]=-inf;sort(p+1,p+n+1);cdq(1,n);FOR(i,1,n)p[i].y=maxx-p[i].y;sort(p+1,p+n+1);cdq(1,n);FOR(i,1,n)p[i].x=maxx-p[i].x;sort(p+1,p+n+1);cdq(1,n);FOR(i,1,n)p[i].y=maxx-p[i].y;sort(p+1,p+n+1);cdq(1,n);FOR(i,1,ans[0])printf("%d\n",ans[i]);return 0;
} 

转载于:https://www.cnblogs.com/Stump/p/7997620.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！