【cogs1752】[BOI2007] Mokia

2015.05.19 11:37 Tue | 23次阅读 | 旧日oi | 固定链接 | 源码

【题目描述】

摩尔瓦多的移动电话公司摩基亚(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,输出一个一行整数,即当前询问矩形内的用户数量。

【输入样例】

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

【输出样例】

3
5

【提示】

输入
输出
意义
0 4
大小为4*4的全零正方形
1 2 3 3
向(2,3)方格加入3名用户
2 1 1 3 3
查询矩形1<=x<=3,1<=y<=3内的用户数量
3
查询结果
1 2 2 2
向(2,2)方格加入2名用户
2 2 2 3 4
查询矩形2<=x<=3,2<=y<=4内的用户数量
5
查询结果
3
终止程序

【数据规模】

1<=W<=2000000
1<=X1<=X2<=W
1<=Y1<=Y2<=W
1<=x,y<=W
0<A<=10000
命令1不超过160000个。
命令2不超过10000个。

题解

CDQ分治裸题,把询问存下,add操作直接存,query操作拆成4个存。
然后二分,处理完前后部分后,考虑前半部分对后半部分的影响,将前半部分,后半部分分别按x排序,然后看看程序就可以懂了,很好理解。
注意最后要把加上的减回去,因为递归回前一层可能会再次加入这些元素。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct Que{
    int x,y,v,tp,_id,id;
    Que(int a,int b,int c,int d,int e,int f):
    x(a),y(b),v(c),tp(d),_id(e),id(f){}
    Que(){}
}q[200000];
int c[2000005],w;
int ans[10005];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y)
{
    for(;x<=w;x+=lowbit(x)) c[x]+=y;
}
int query(int x)
{
    int ret=0;
    for(;x;x-=lowbit(x)) ret+=c[x];
    return ret;
}
bool cmp(const Que &a,const Que &b)
{
    return a.x<b.x;
}
void cdq(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    sort(q+l,q+mid+1,cmp);
    sort(q+mid+1,q+r+1,cmp);
    int now=l;
    for(int i=mid+1;i<=r;i++)
    {
        while(now<=mid&&q[now].x<=q[i].x) 
        {
            if(q[now].tp==1) add(q[now].y,q[now].v);
            now++;
        }
        if(q[i].tp==2) ans[q[i]._id]+=q[i].v*query(q[i].y);
    }
    for(int i=l;i<now;i++)
    if(q[i].tp==1) add(q[i].y,-q[i].v);
}
int main()
{
    freopen("mokia.in","r",stdin);
    freopen("mokia.out","w",stdout);
    int op,a,b,c,d,id=0,tot=0;
    while(scanf("%d",&op)&&op!=3)
    {
        if(op==0) scanf("%d",&w);
        else if(op==1) 
        {
            scanf("%d%d%d",&a,&b,&c);
            q[++id]=Que(a,b,c,1,0,id);
        }
        else
        {
            tot++;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            q[++id]=Que(a-1,b-1,1,2,tot,id);
            q[++id]=Que(c,d,1,2,tot,id);
            q[++id]=Que(a-1,d,-1,2,tot,id);
            q[++id]=Que(c,b-1,-1,2,tot,id);
        }
    }
    cdq(1,id);
    for(int i=1;i<=tot;i++) printf("%d\n",ans[i]);
}```