[Violet]天使玩偶/SJY摆棋子
CDQ分治，归并排序写错调了一天可海星
考虑哈夫曼距离特点：
$$dis(A,B)=|A_x-B_x|+|A_y-B_y|$$
若能够把绝对值去掉岂不是很妙！
$$dis(A,B)=(A_x+A_y)-(B_x+B_y)$$
由于A坐标已经定下来了，我们只要找B坐标使得$B_x+B_y$ 最大，就可以是距离最小了！
然后套上CDQ三维偏序求解就好了
因为不一定每个点都在当前询问点的左下方（也就是说绝对值不能直接去掉，我们把所有点转个方向再做3遍就吼了）
Tip:这道题卡常，请使用归并排序，并且求解区间最值时不要使用线段树，改用树状数组！！
（虽然某人说正常人用的都是树状数组，可我开始就是用线段树了..）
1 #include<bits/stdc++.h> 2 #define lowbit(x) ((x)&(-x)) 3 #define writeln(x) write(x),puts("") 4 #define writep(x) write(x),putchar(' ') 5 using namespace std; 6 inline int read(){ 7 int ans=0,f=1;char chr=getchar(); 8 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 9 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 10 return ans*f; 11 }void write(int x){ 12 if(x<0) putchar('-'),x=-x; 13 if(x>9) write(x/10); 14 putchar(x%10+'0'); 15 }const int M = 1e6+5; 16 int n,m,tot,s[M],maxx,maxy,maxn,ans[M]; 17 struct P{int x,y,id,type;}q[M],p[M],h[M]; 18 inline void cmax(int &x,int y){if(x<y)x=y;} 19 inline void cmin(int &x,int y){if(x>y)x=y;} 20 inline void Add(int x,int y) {for(;x<=maxn;x+=lowbit(x))cmax(s[x],y);} 21 inline void Clear(int x) {for(;x<=maxn;x+=lowbit(x))s[x]=0;} 22 inline int Max(int x){int ans=0;for(;x;x-=lowbit(x))cmax(ans,s[x]);return ans;} 23 void Solve(int l,int r){ 24 if(l==r) return; 25 int mid=l+r>>1; 26 Solve(l,mid),Solve(mid+1,r); 27 int j=l,ll=l,rr=mid+1,nn=l-1; 28 for(int i=mid+1;i<=r;i++){ 29 while(i<=r&&p[i].type!=2) ++i;if(i>r) break; 30 for(;j<=mid&&p[j].x<=p[i].x;++j)if(p[j].type==1)Add(p[j].y,p[j].y+p[j].x); 31 int t=Max(p[i].y); 32 if(t) cmin(ans[p[i].id],p[i].x+p[i].y-t); 33 } 34 for(int i=l;i<j;i++)if(p[i].type==1) Clear(p[i].y); 35 while(ll<=mid&&rr<=r){ 36 if(p[ll].x<=p[rr].x) h[++nn]=p[ll++]; 37 else h[++nn]=p[rr++]; 38 } 39 while(ll<=mid) h[++nn]=p[ll++]; 40 while(rr<=r) h[++nn]=p[rr++]; 41 for(int i=l;i<=r;i++) p[i]=h[i]; 42 } 43 int main(){ 44 n=read(),m=read(); 45 for(int x,y,i=1;i<=n;i++)x=read(),y=read(),q[++tot]=(P){x+1,y+1,i,1},cmax(maxx,x+1),cmax(maxy,y+1); 46 for(int x,y,opt,i=1;i<=m;i++){ 47 opt=read(),x=read(),y=read(); 48 cmax(maxx,x+1),cmax(maxy,y+1); 49 if(opt==1) q[++tot]=(P){x+1,y+1,i+n,1}; 50 else q[++tot]=(P){x+1,y+1,i+n,2}; 51 }n+=m;memset(ans,0x3f,sizeof(ans)); 52 maxn=max(maxx,maxy)+1; 53 for(int i=1;i<=n;i++) p[i]=q[i]; 54 Solve(1,n); 55 for(int i=1;i<=n;i++) p[i]=q[i],p[i].x=maxn-p[i].x; 56 Solve(1,n); 57 for(int i=1;i<=n;i++) p[i]=q[i],p[i].y=maxn-p[i].y; 58 Solve(1,n); 59 for(int i=1;i<=n;i++) p[i]=q[i],p[i].x=maxn-p[i].x,p[i].y=maxn-p[i].y; 60 Solve(1,n); 61 for(int i=1;i<=n;i++)if(q[i].type==2) printf("%d\n",ans[i]); 62 return 0; 63 }
查看12道真题和解析
