[BOI2007] Mokia

题目描述

摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户C的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。

在定位系统中，世界被认为是一个W×W的正方形区域，由1×1的方格组成。每个方格都有一个坐标(x,y)，1<=x,y<=W。坐标的编号从1开始。对于一个4×4的正方形，就有1<=x<=4,1<=y<=4（如图）：

请帮助Mokia公司编写一个程序来计算在某个矩形区域内有多少名用户。

输入输出格式

输入格式：

有三种命令，意义如下：

命令参数意义

0 W 初始化一个全零矩阵。本命令仅开始时出现一次。
1 x y A 向方格(x,y)中添加A个用户。A是正整数。
2 X1 Y1 X2 Y2 查询X1<=x<=X2，Y1<=y<=Y2所规定的矩形中的用户数量
3 无参数结束程序。本命令仅结束时出现一次。

输出格式：

对所有命令2，输出一个一行整数，即当前询问矩形内的用户数量。

输入输出样例

输入样例#1：

输出样例#1：

3

5

说明

1<=W<=2000000

1<=X1<=X2<=W

1<=Y1<=Y2<=W

1<=x,y<=W

0<A<=10000

命令1不超过160000个。

命令2不超过10000个。

CDQ求解三维偏序模板题。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=200005;

struct node{

    int x,y,z,num,FL;

}a[maxn];

int opt,A,B,C,D,cnt=0,W,qnum;

int ans[maxn],f[maxn],T;

inline bool cmp3(node x,node y){

    return x.z==y.z?x.num<y.num:x.z<y.z;

}

inline bool cmp2(node x,node y){

    return x.y==y.y?cmp3(x,y):x.y<y.y;

}

inline bool cmp1(node x,node y){

    return x.x==y.x?cmp2(x,y):x.x<y.x;

}

inline void update(int x,int y){

    for(;x<=T;x+=x&-x) f[x]+=y;

}

inline int query(int x){

    int an=0;

    for(;x;x-=x&-x) an+=f[x];

    return an;

}

void cdq(int L,int R){

    if(L>=R) return;

    int mid=L+R>>1,i,j;

    cdq(L,mid),cdq(mid+1,R);

    sort(a+L,a+mid+1,cmp2);

    sort(a+mid+1,a+R+1,cmp2);

    for(i=L,j=mid+1;j<=R;j++){

        for(;i<=mid&&a[i].y<=a[j].y;i++) if(!a[i].num) update(a[i].z,a[i].FL);

        if(a[j].num) ans[a[j].num]+=a[j].FL*query(a[j].z);

    }

    for(i--;i>=L;i--) if(!a[i].num) update(a[i].z,-a[i].FL);

}

int main(){

    scanf("%d%d",&opt,&W);

    while(scanf("%d",&opt)==1&&opt!=3){

        T++;

        if(opt==1){

            scanf("%d%d%d",&A,&B,&C);

            a[++cnt]=(node){A,B,T,0,C};

        }

        else{

            qnum++;

            scanf("%d%d%d%d",&A,&B,&C,&D);

            a[++cnt]=(node){C,D,T,qnum,1};

            a[++cnt]=(node){A-1,B-1,T,qnum,1};

            a[++cnt]=(node){A-1,D,T,qnum,-1};

            a[++cnt]=(node){C,B-1,T,qnum,-1};

        }

    }

    sort(a+1,a+cnt+1,cmp1);

    cdq(1,cnt);

    for(int i=1;i<=qnum;i++) printf("%d\n",ans[i]);

    return 0;

}

巴特西

[BOI2007] Mokia

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章