Luogu | P2163 [SHOI 2007] 园丁的烦恼 | 离线 | 树状数组 / cdq 分治


Description

很久很久以前,在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者,在他的皇家花园里种植着各种奇花异草。

有一天国王漫步在花园里,若有所思,他问一个园丁道: “最近我在思索一个问题,如果我们把花坛摆成六个六角形,那么……”

“那么本质上它是一个深度优先搜索,陛下。”园丁深深地向国王鞠了一躬。

“嗯……我听说有一种怪物叫九头蛇,它非常贪吃苹果树……”

“是的,显然这是一道经典的动态规划题,早在N元4002年我们就已经发现了其中的奥秘了,陛下。”

“该死的,你究竟是什么来头?”

“陛下息怒,干我们的这行经常莫名其妙地被问到和OI有关的题目,我也是为了预防万一啊!” 王者的尊严受到了伤害,这是不可容忍的。

看来一般的难题是难不倒这位园丁的,国王最后打算用车轮战来消耗他的实力: “年轻人,在我的花园里的每一棵树可以用一个整数坐标来表示,一会儿,我的骑士们会来轮番询问你某一个矩阵内有多少树,如果你不能立即答对,你就准备走人吧!”说完,国王气呼呼地先走了。

这下轮到园丁傻眼了,他没有准备过这样的问题。所幸的是,作为“全国园丁保护联盟”的会长——你,可以成为他的最后一根救命稻草。


Input Format

第一行有两个整数 $n$,$m$ 。$n$ 代表皇家花园的树木的总数,$m$ 代表骑士们询问的次数。

文件接下来的 $n$ 行,每行都有两个整数 $x_i$,$y_i$,代表第 $i$ 棵树的坐标。

文件的最后 $m$ 行,每行都有四个整数$a_j,b_j,c_j,d_j$,表示第 $j$ 次询问,其中所问的矩形以 $(a_j,b_j)$ 为左下坐标,以 $(c_j,d_j)$ 为右上坐标。


Output Format

共输出 $m$ 行,每行一个整数,即回答国王以 $(a_j,b_j)$ 和 $(c_j,d_j)$ 为界的矩形里有多少棵树。


Input Sample

Sample 01

3 1
0 0
0 1
1 0
0 0 1 1


Output Sample

Sample 01

3


Data Range

$1 \le n,m \le 5\times 10^5$,$0 \le x,y \le 10^7$。


Solution

可以将查询拆分成四个从 $(1,1)$ 开始的查询。

将操作按照 $x$ 排序,然后用数据结构处理 $y$ 即可。当然用 cdq 分治也未尝不可。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define lowbit(x) (x&(-x))

using std::sort;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct pt{
    int x;
    int y;
    int id;
    int type;
    friend bool operator < (pt a,pt b){
        if(a.x==b.x){
            if(a.y==b.y){
                if(a.type==b.type)
                    return a.id<b.id;
                return a.type*a.type<b.type*b.type;
            }
            return a.y<b.y;
        }
        return a.x<b.x;
    }
}S[3000005];

int N;
int Q;
int cnt;
int siz;
int maxx;
int maxy;

int ans[500005];
int bit[2000005];

int DiscX[10000005];
int DiscY[10000005];

void BITadd(int u){
    if(u<0)
        return;
    while(u<=DiscY[maxy]){
        bit[u]++;
        u+=lowbit(u);
    }
    return;
}

int BITquery(int u){
    if(u<0)
        return 0;
    int ret=0;
    while(u){
        ret+=bit[u];
        u-=lowbit(u);
    }
    return ret;
}

int main(){
    int lx,ly,rx,ry;
    Read(N);
    Read(Q);
    rep(i,1,N){
        cnt++;
        Read(S[cnt].x);
        Read(S[cnt].y);
        S[cnt].id=i;
        S[cnt].type=0;
        DiscX[S[cnt].x]=1;
        DiscY[S[cnt].y]=1;
        maxx=max(maxx,S[cnt].x);
        maxy=max(maxy,S[cnt].y);
    }
    rep(i,1,Q){
        Read(lx);
        Read(ly);
        Read(rx);
        Read(ry);
        lx--;
        ly--;
        S[++cnt]=(pt){rx,ry,i,1};
        S[++cnt]=(pt){lx,ry,i,-1};
        S[++cnt]=(pt){lx,ly,i,1};
        S[++cnt]=(pt){rx,ly,i,-1};
        if(lx>=0)
            DiscX[lx]=1;
        if(ly>=0)
            DiscY[ly]=1;
        DiscX[rx]=1;
        DiscY[ry]=1;
        maxx=max(maxx,rx);
        maxy=max(maxy,ry);
    }
    rep(i,1,maxx)
        DiscX[i]+=DiscX[i-1];
    rep(i,1,maxy)
        DiscY[i]+=DiscY[i-1];
    rep(i,1,cnt){
        if(S[i].x>=0)
            S[i].x=DiscX[S[i].x];
        if(S[i].y>=0)
            S[i].y=DiscY[S[i].y];
    }
    sort(S+1,S+1+cnt);
    rep(i,1,cnt)
        if(S[i].type==0)
            BITadd(S[i].y);
        else
            ans[S[i].id]+=S[i].type*BITquery(S[i].y);
    rep(i,1,Q)
        printf("%d\n",ans[i]);
    return 0;
}