[BZOJ1935][SHOI2007]Tree 园丁的烦恼（离线+树状数组）

题意

给出第一象限的n个点，有m次询问，每次询问一个矩形中的点的个数.(0<=n,m<=500000，0<=xi,yi<=10000000)

题解

一眼望去不可做。

用二位前缀和的思想，一个矩形可以用以坐标轴为一对临边的四个矩形加减得到。

考虑离线，离散化。所以我们要求的只是若干个以坐标轴为一对临边的矩形的权值。

但还是不可做。

转化为序列问题，我们要求的矩形面积，其实就是每行前缀和的一段连续地和。

具体一些，就是，算出每一行的前缀和，对于横坐标相等的前缀和，我们维护他们，矩形的面积，就是这些前缀和的前面一段。同时维护一个横坐标指针x，在x右移时前缀和加上横坐标为x的点。我们发现这些操作可以用树状数组维护。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int const N=;

 int head[N],hed[N],c[N],n,m;

 int cnt,cntx,cnty,totx,toty,ans[N],tot,x[N],y[N];

 struct zb{

     int x,y;

 }zb[N];

 struct ask{

     int x,xx,y,yy;

 }q[N];

 struct edge{

     int to,nxt;

 }e[N];

 struct hhh{

     int to,nxt,w,id;

 }f[N];

 void add(int u,int v){

     cnt++;

     e[cnt].nxt=head[u];

     e[cnt].to=v;

     head[u]=cnt;

 }

 void ad(int u,int v,int c,int x){

     tot++;

     f[tot].nxt=hed[u];

     f[tot].w=c;

     f[tot].to=v;

     f[tot].id=x;

     hed[u]=tot;

 }

 int lowbit(int x){

     return x&-x;

 }

 void update(int x,int w){

     for(int i=x;i<=cnty;i+=lowbit(i)){

         c[i]+=;

     }

 }

 int check(int x,int w){

     if(x==)return ;

     int ans=;

     for(int i=x;i>=;i-=lowbit(i)){

         ans+=c[i];

     }

     return ans*w;

 }

 void work(){

     for(int i=;i<=cntx;i++){

         for(int j=head[i];j;j=e[j].nxt){

             int v=e[j].to;

             update(v,);

         }

         for(int j=hed[i];j;j=f[j].nxt){

             int v=f[j].to;

             ans[f[j].id]+=check(v,f[j].w);

         }

     }

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         scanf("%d%d",&zb[i].x,&zb[i].y);

         x[++totx]=zb[i].x;

         y[++toty]=zb[i].y;

     }

     for(int i=;i<=m;i++){

         scanf("%d%d%d%d",&q[i].x,&q[i].y,&q[i].xx,&q[i].yy);

         x[++totx]=q[i].x;

         y[++toty]=q[i].y;

         x[++totx]=q[i].xx;

         y[++toty]=q[i].yy;

     }

     sort(x+,x++totx);

     sort(y+,y++toty);

     cntx=unique(x+,x++totx)-(x+);

     cnty=unique(y+,y++toty)-(y+);

     for(int i=;i<=n;i++){

         zb[i].x=lower_bound(x+,x++cntx,zb[i].x)-x;

         zb[i].y=lower_bound(y+,y++cnty,zb[i].y)-y;

         add(zb[i].x,zb[i].y);

     }

     for(int i=;i<=m;i++){

         q[i].x=lower_bound(x+,x++cntx,q[i].x)-x;

         q[i].y=lower_bound(y+,y++cnty,q[i].y)-y;

         q[i].xx=lower_bound(x+,x++cntx,q[i].xx)-x;

         q[i].yy=lower_bound(y+,y++cnty,q[i].yy)-y;

         ad(q[i].x-,q[i].y-,,i);

         ad(q[i].xx,q[i].yy,,i);

         ad(q[i].x-,q[i].yy,-,i);

         ad(q[i].xx,q[i].y-,-,i);

     }

     work();

     for(int i=;i<=m;i++){

         printf("%d\n",ans[i]);

     }

     return ;

 }

巴特西

[BZOJ1935][SHOI2007]Tree 园丁的烦恼（离线+树状数组）

题意

给出第一象限的n个点，有m次询问，每次询问一个矩形中的点的个数.(0<=n,m<=500000，0<=xi,yi<=10000000)

题解

一眼望去不可做。

用二位前缀和的思想，一个矩形可以用以坐标轴为一对临边的四个矩形加减得到。

考虑离线，离散化。所以我们要求的只是若干个以坐标轴为一对临边的矩形的权值。

但还是不可做。

转化为序列问题，我们要求的矩形面积，其实就是每行前缀和的一段连续地和。

最新文章

热门文章