bzoj 2716 天使玩偶（CDQ分治，BIT）

【题目链接】

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=29234

【题意】

询问当前点与已知点的最小曼哈顿距离。

【思路】

CDQ分治

Dist(A,B)=|A.x-B.x|+|A.y-B.y|。假设B处于A点的左下方，则有dist=(A.x+A.y)-(B.x+B.y)，然后发现这个就与刚做过的 Mokia 比较相似，只不过是求和变成了求取最大罢了，依然可以对x用cdq分治使升序，对y用树状数组维护统计。

再考虑其它的相对位置就行了。这里有个好（qi）的（ji）方（yin）法（qiao），就是通过把a变成mx-a+1来改变符号的方向，所以只需要写一个处理其中一种情况的函数就可以套用于其他情况了。

【代码】

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #define FOR(a,b,c) for(int a=b;a<=c;a++)
  6 using namespace std;
  7 
  8 const int N = 1e6+10;
  9 const int inf = 1e9+10;
 10 
 11 void read(int& x)
 12 {
 13     char c=getchar(); x=0; int f=1;
 14     while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
 15     while(isdigit(c)) x=x*10+c-'0',c=getchar();
 16     x*=f;
 17 }
 18 
 19 int n,m,mx,sz,T,C[N],flag[N];
 20 
 21 struct Node {
 22     int t,x,y,pos,ans;
 23     bool operator < (const Node& rhs) const{
 24         return x<rhs.x;
 25     }
 26     Node(int t=0,int x=0,int y=0) {
 27         this->t=t,this->x=x,this->y=y;
 28         pos=sz; ans=inf;
 29     }
 30 }q[N],t[N];
 31 bool cmp(const Node& x,const Node& y)
 32 {
 33     return x.pos<y.pos;
 34 }
 35 
 36 
 37 void upd(int x,int v)
 38 {
 39     for(;x<=mx;x+=x&-x) {
 40         if(flag[x]!=T)  flag[x]=T,C[x]=v;
 41         else C[x]=max(C[x],v);
 42     }
 43 }
 44 int query(int x)
 45 {
 46     int res=0;
 47     for(;x;x-=x&-x) {
 48         if(flag[x]==T) res=max(res,C[x]);
 49     }
 50     return res;
 51 }
 52 
 53 void solve(int l,int r)
 54 {
 55     if(l==r) return ;
 56     int mid=(l+r)>>1;
 57     int l1=l,l2=mid+1,i,j;
 58     for(i=l;i<=r;i++) {
 59         if(q[i].pos<=mid) t[l1++]=q[i];
 60         else t[l2++]=q[i];
 61     }
 62     memcpy(q+l,t+l,sizeof(Node)*(r-l+1));
 63     solve(l,mid);
 64     j=l; T++;
 65     for(i=mid+1;i<=r;i++) if(q[i].t==2) {
 66         for(;j<=mid&&q[j].x<=q[i].x;j++)
 67             if(q[j].t==1) upd(q[j].y,q[j].y+q[j].x);
 68         int tmp=query(q[i].y);
 69         if(tmp) q[i].ans=min(q[i].ans,q[i].x+q[i].y-tmp);
 70     }
 71     solve(mid+1,r);
 72     l1=l,l2=mid+1; int now=l;
 73     while(l1<=mid||l2<=r) {
 74         if(l2>r||l1<=mid&&q[l1]<q[l2]) t[now++]=q[l1++];
 75         else t[now++]=q[l2++];
 76     }
 77     memcpy(q+l,t+l,sizeof(Node)*(r-l+1));
 78 }
 79 
 80 
 81 int main()
 82 {
 83     //freopen("in.in","r",stdin);
 84     //freopen("out.out","w",stdout);
 85     read(n),read(m);
 86     int t,x,y;
 87     FOR(i,1,n) {
 88         read(x),read(y);
 89         q[++sz]=Node(1,x,y);
 90         mx=max(mx,y);
 91     }
 92     FOR(i,1,m) {
 93         read(t),read(x),read(y);
 94         q[++sz]=Node(t,x,y);
 95         mx=max(mx,y);
 96     }
 97     sort(q+1,q+sz+1);
 98     solve(1,sz);
 99     FOR(i,1,sz) q[i].x=mx-q[i].x+1;
100     sort(q+1,q+sz+1);
101     solve(1,sz);
102     FOR(i,1,sz) q[i].y=mx-q[i].y+1;
103     sort(q+1,q+sz+1);
104     solve(1,sz);
105     FOR(i,1,sz) q[i].x=mx-q[i].x+1;
106     sort(q+1,q+sz+1);
107     solve(1,sz);
108     sort(q+1,q+sz+1,cmp);
109     FOR(i,n+1,sz) if(q[i].t==2)
110         printf("%d
",q[i].ans);
111     return 0;
112 }

Ps：手残毁一生 <_<