首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。