首页 > 代码库 > BZOJ1120 : [POI2009]STR

BZOJ1120 : [POI2009]STR

因为问题的对称性,只需要考虑求出有多少点离$A$更近即可。

枚举$4$个绝对值的正负号,可以解出坐标范围。

若可以转化为二维数点,则可以统一扫描线+树状数组解决。

否则是三维数点,按一维排序,剩下两维维护KD-Tree即可。

时间复杂度$O(n\sqrt{n})$。

 

#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int N=100010;int W,H,n,m,i,j,A,B,C,D,X,Y,ans[N*2];struct P{int x,y;}a[N];inline bool cmpx(const P&a,const P&b){return a.x<b.x;}inline bool cmpXY(int x,int y){return X*a[x].x+Y*a[x].y<X*a[y].x+Y*a[y].y;}inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}inline void umin(int&a,int b){if(a>b)a=b;}inline void umax(int&a,int b){if(a<b)a=b;}namespace RangeQuery{struct E{  int x,l,r,t;  E(){}  E(int _x,int _l,int _r,int _t){x=_x,l=_l,r=_r,t=_t;}}e[N*20];int cnt,v[N],bit[N];inline bool cmp(const E&a,const E&b){return a.x<b.x;}inline void addquery(int xl,int xr,int yl,int yr,int o){  e[++cnt]=E(xr,yl,yr,o);  e[++cnt]=E(xl-1,yl,yr,-o);}inline int getl(int x){  int l=1,r=n,mid,t=n+1;  while(l<=r)if(v[mid=(l+r)>>1]>=x)r=(t=mid)-1;else l=mid+1;  return t;}inline int getr(int x){  int l=1,r=n,mid,t=0;  while(l<=r)if(v[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;  return t;}inline void add(int x){for(;x<=n;x+=x&-x)bit[x]++;}inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}void solve(){  sort(e+1,e+cnt+1,cmp);  for(i=1;i<=n;i++)v[i]=a[i].y;  sort(v+1,v+n+1);  sort(a+1,a+n+1,cmpx);  for(i=j=1;i<=cnt;i++){    while(j<=n&&a[j].x<=e[i].x)add(getl(a[j++].y));    int l=getl(e[i].l),r=getr(e[i].r);    if(l>r)continue;    int t=ask(r)-ask(l-1);    if(e[i].t>0)ans[e[i].t]+=t;else ans[-e[i].t]-=t;  }}}namespace KDTree{int q[N],id[N],root,cmp_d,cnt,ret;struct node{int d[2],l,r,Max[2],Min[2],val,sum,f;}t[N];inline bool cmp(const node&a,const node&b){return a.d[cmp_d]<b.d[cmp_d];}struct E{  int A,B,C,xl,xr,yl,yr,o;  E(){}  E(int _A,int _B,int _C,int _xl,int _xr,int _yl,int _yr,int _o){    A=_A,B=_B,C=_C,o=_o;    xl=_xl,xr=_xr,yl=_yl,yr=_yr;  }}e[N*2];inline bool cmpE(const E&a,const E&b){return a.C<b.C;}inline void up(int x){  if(t[x].l){    umax(t[x].Max[0],t[t[x].l].Max[0]);    umin(t[x].Min[0],t[t[x].l].Min[0]);    umax(t[x].Max[1],t[t[x].l].Max[1]);    umin(t[x].Min[1],t[t[x].l].Min[1]);  }  if(t[x].r){    umax(t[x].Max[0],t[t[x].r].Max[0]);    umin(t[x].Min[0],t[t[x].r].Min[0]);    umax(t[x].Max[1],t[t[x].r].Max[1]);    umin(t[x].Min[1],t[t[x].r].Min[1]);  }}int build(int l,int r,int D,int f){  int mid=(l+r)>>1;  cmp_d=D;nth_element(t+l+1,t+mid+1,t+r+1,cmp);  id[t[mid].f]=mid;  t[mid].f=f;  t[mid].Max[0]=t[mid].Min[0]=t[mid].d[0];  t[mid].Max[1]=t[mid].Min[1]=t[mid].d[1];  if(l!=mid)t[mid].l=build(l,mid-1,!D,mid);  if(r!=mid)t[mid].r=build(mid+1,r,!D,mid);  return up(mid),mid;}void init(){  for(i=1;i<=n;i++)t[i].d[0]=a[i].x,t[i].d[1]=a[i].y,t[i].f=i;  root=build(1,n,0,0);  sort(e+1,e+cnt+1,cmpE);}inline void addquery(int A,int B,int C,int xl,int xr,int yl,int yr,int o){  e[++cnt]=E(A,B,C,xl,xr,yl,yr,o);}inline void change(int x){for(t[x].val=1;x;x=t[x].f)t[x].sum++;}void ask(int x){  if(!t[x].sum||t[x].Max[0]<A||t[x].Min[0]>B||t[x].Max[1]<C||t[x].Min[1]>D)return;  if(t[x].Min[0]>=A&&t[x].Max[0]<=B&&t[x].Min[1]>=C&&t[x].Max[1]<=D){ret+=t[x].sum;return;}  if(t[x].val&&t[x].d[0]>=A&&t[x].d[0]<=B&&t[x].d[1]>=C&&t[x].d[1]<=D)ret++;  if(t[x].l)ask(t[x].l);  if(t[x].r)ask(t[x].r);}void solve(int _X,int _Y){  X=_X,Y=_Y;  for(i=1;i<=n;i++)t[i].val=t[i].sum=0;  for(i=1;i<=n;i++)q[i]=i;  sort(q+1,q+n+1,cmpXY);  for(i=j=1;i<=cnt;i++)if(e[i].A==X&&e[i].B==Y){    while(j<=n&&X*a[q[j]].x+Y*a[q[j]].y<e[i].C)change(id[q[j++]]);    ret=0;    A=e[i].xl,B=e[i].xr,C=e[i].yl,D=e[i].yr;    ask(root);    ans[e[i].o]+=ret;  }}}inline void deal(int A,int B,int C,int D,int o){  for(int S=0;S<16;S++){    ll c=0;int a=0,b=0,xl=1,xr=W,yl=1,yr=H;    if(S&1)a++,c-=A,umax(xl,A);else a--,c+=A,umin(xr,A-1);    if(S&2)b++,c-=B,umax(yl,B);else b--,c+=B,umin(yr,B-1);    if(S&4)a--,c+=C,umax(xl,C);else a++,c-=C,umin(xr,C-1);    if(S&8)b--,c+=D,umax(yl,D);else b++,c-=D,umin(yr,D-1);    if(xl>xr||yl>yr)continue;    if(!a&&!b&&c>=0)continue;    if(a||b){      a/=2,b/=2;      if(c%2==0||c>0)c/=2;else c=c/2-1;    }    int _c=c;    if(a<0&&!b)umax(xl,_c+1);    if(a>0&&!b)umin(xr,-_c-1);    if(b<0&&!a)umax(yl,_c+1);    if(b>0&&!a)umin(yr,-_c-1);    if(xl>xr||yl>yr)continue;    if(!a||!b)RangeQuery::addquery(xl,xr,yl,yr,o);    else KDTree::addquery(a,b,-c,xl,xr,yl,yr,o);  }}int main(){  read(W),read(H),read(n),read(m);  for(i=1;i<=n;i++)read(a[i].x),read(a[i].y);  for(i=1;i<=m;i++){    read(A),read(B),read(C),read(D);    deal(A,B,C,D,i*2-1);    deal(C,D,A,B,i*2);  }  RangeQuery::solve();  KDTree::init();  KDTree::solve(-1,-1);  KDTree::solve(-1,1);  KDTree::solve(1,-1);  KDTree::solve(1,1);  for(i=1;i<=m;i++)printf("%d %d %d\n",ans[i*2-1],ans[i*2],n-ans[i*2-1]-ans[i*2]);  return 0;}

  

BZOJ1120 : [POI2009]STR