bzoj1935 [Shoi2007]园丁的烦恼

bzoj1935 [Shoi2007]园丁的烦恼

有N个点坐标为(xi,yi)，M次询问，询问(a,b)-(c,d)的矩形内有多少点。

0≤n≤500000，1≤m≤500000，0≤xi，yi≤10000000

看完数据范围傻眼系列。

做法：

离线处理

因为这个范围肯定不能把x y都离散，

所以只把点和询问的y坐标放在一起都离散化，然后一起按x坐标排序，

再开一个树状数组，求出每个需要的点的二维前缀和。

不理解的话拿画图板画一下就好了。

细节见代码

#include<bits/stdc++.h>
#define MAXN 500005
#define lowbit(a) (a&-a)
using namespace std;
inline int read(){
    int x=0,t=1;char c;c=getchar();
    while(c<'0'||c>'9'){if(c=='-')t=-1;c=getchar();} 
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();} 
    return x*t;
} 
int N,M,Y[3*MAXN],cnt,tx[MAXN],ty[MAXN],sum[MAXN][5],
xa[MAXN],ya[MAXN],xb[MAXN],yb[MAXN],c[MAXN*3],siz;
struct Work{
    int x,y,id,f;
    bool operator <(const Work z)const{
        return x<z.x||(x==z.x&&f<z.f);
    }
}a[5*MAXN];
inline void add(int pos,int val){
    for(;pos<=siz;pos+=lowbit(pos))
        c[pos]+=val;
}
inline int query(int pos){
    int s=0;
    for(;pos>0;pos-=lowbit(pos))
        s+=c[pos];
    return s;
}
int main()
{
    N=read(),M=read();
    for(int i=1;i<=N;i++){
        tx[i]=read()+1,ty[i]=read();
        Y[++cnt]=ty[i];
    }
    for(int i=1;i<=M;i++){
        xa[i]=read()+1,ya[i]=read(),xb[i]=read()+1,yb[i]=read();
        Y[++cnt]=ya[i],Y[++cnt]=yb[i];
    }
    sort(Y+1,Y+1+cnt);
    siz=unique(Y+1,Y+1+cnt)-Y-1;    cnt=0;
    for(int i=1;i<=N;i++){
        ty[i]=lower_bound(Y+1,Y+1+siz,ty[i])-Y;       //把点和询问放在一起离散化，然后排序。
        a[++cnt]=(Work){tx[i],ty[i],0,0};
    }
    for(int i=1;i<=M;i++){
        ya[i]=lower_bound(Y+1,Y+1+siz,ya[i])-Y;
        yb[i]=lower_bound(Y+1,Y+1+siz,yb[i])-Y;
        a[++cnt]=(Work){xb[i],  yb[i],  i,1};         //把需要计算矩阵和需要的四个点加进操作数组中，二位前缀和不用解释吧。
        a[++cnt]=(Work){xa[i]-1,ya[i]-1,i,2};
        a[++cnt]=(Work){xa[i]-1,yb[i],i,3}; 
        a[++cnt]=(Work){xb[i],ya[i]-1,i,4};
    }
    sort(a+1,a+1+cnt);
    for(int i=1;i<=cnt;i++){
        if(a[i].id)　　　　　　　　　　　　　　　　　　　  　//遇到点把他加进树状数组
            sum[a[i].id][a[i].f]=query(a[i].y);
        else 
            add(a[i].y,1);
    } 
    for(int i=1;i<=M;i++)
        printf("%d
",sum[i][1]+sum[i][2]-sum[i][3]-sum[i][4]);
    return 0;
}

附个离散写法

sort -> unique -> lower_bound