COGS1752. [BOI2007]摩基亚Mokia

1752. [BOI2007]摩基亚Mokia

★★☆ 输入文件：mokia.in 输出文件：mokia.out 简单对比
时间限制：5 s 内存限制：128 MB

【题目描述】

摩尔瓦多的移动电话公司摩基亚（

在定位系统中，世界被认为是一个

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

【输入格式】

有三种命令，意义如下：

命令	参数	意义
0	W	初始化一个全零矩阵。本命令仅开始时出现一次。
1	x y A	向方格
2	X1 Y1 X2 Y2	查询
3	无参数	结束程序。本命令仅结束时出现一次。

【输出格式】

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

【输入样例】

0 4

1 2 3 3

2 1 1 3 3

1 2 2 2

2 2 2 3 4

【输出样例】

【提示】

输入	输出	意义
0 4		大小为
1 2 3 3		向
2 1 1 3 3		查询矩形
	3	查询结果
1 2 2 2		向
2 2 2 3 4		查询矩形
	5	查询结果
3		终止程序

【数据规模】

命令1不超过

命令2不超过

【来源】

Balkan Olypiad in Informatics 2007,

　　这个问题是 IOI 2000 Mobile 的加强版： Mobile 中 W≤1000，就可以利用二树

状数组在 O(log 2 2 n)的时间复杂度内维护出操作 1)和操作 2)．这个问题中 W 很大，

开二维树状数组 O(W 2 )的空间显然吃不消，考虑使用动态空间的线段树，最多可

能达到操作次数 * (log 2 W) 2 个节点，也相当大了．考虑使用分治思想来解决问题：

　　将操作 1)和操作 2)按顺序看成是一个个事件，假设共有 Tot 个事件，

Tot≤170000．类似例题一，我们定义 Solve(l, r)表示对于每一个 Query 操作的事

件 i，将 l ..i-1 的 Add 操作的所有属于 i 的矩形范围内的数值累加进来．目标是

Solve(1, n)．

　　假设计算 Solve(L, R)，递归 Solve(L, Mid)，Solve(Mid + 1, r)后，对 L .. Mid

的所有 Add 操作的数值累加到 Mid + 1 .. R 的所有匹配的 Query 操作的矩形中．

后面这个问题等价于：平面中有 p 个点，q 个矩形，每个点有一个权值，求

每个矩形内的点的权值之和．这个问题只需要对所有的点以及矩形的左右边界进

行排序，用一维树状数组或线段树在 O((p+q)log 2 W)的时间复杂度即可维护得出．

因此问题的总的时间复杂度为 O(Tot*log 2 Tot*log 2 W)，不会高于二维线段树的

O(Tot*log 2 W*log 2 W)的时间复杂度．

　　上述这个算法无论是编程复杂度还是空间复杂度都比使用二维线段树优秀，

分治思想又一次得到了很好的应用．在这个问题中，利用分治思想我们将一个在

线维护的问题转化成一个离线问题，将二维线段树解决的问题降维用一维线段树

来解决，使得问题变得更加简单．

　　　　　　　　　　　　——引自《从《Cash》谈一类分治算法的应用cdq》

==============================================

哔哩吧啦，讲了一大片。

不知道你们听懂了吗？反正我是没听懂。

但这并不妨碍我们A掉这道题。

一句话概括CDQ分治思想：整体考虑[l,mid]对[mid+1,r]的影响

整体二分递归调用时，mid前的区间对mid后的区间会产生有且仅有一次影响，不重不漏。（可能描述不太准确）

还有一点，cdq分治思想主要体现在将不断变化的决策转化成一个不变的决策集合，将在线转化为离线

然后……还是看代码吧。（because不太好描述）

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4e5+5;
struct node{
    int x1,x2,y,f,id;
    node(){}
    node(int x1,int x2,int y,int f,int id):x1(x1),x2(x2),y(y),f(f),id(id){}
    bool operator <(const node &a)const{
        if(y!=a.y) return y<a.y;
        return id<a.id;
    }
}q[N],s1[N],s2[N];
int m,id_cnt,cnt,BIT[N],a[N],ans[N];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline int hash(int x,int l=1,int r=cnt){
    while(l<r){
        int mid=l+r>>1;
        if(x<=a[mid]) r=mid;
        else l=mid+1;
    }
    return l;
}
inline int lowbit(int x){
    return x&-x;
}
inline void updata(int x,int v){
    for(int i=x;i<=cnt;i+=lowbit(i)) BIT[i]+=v;
}
inline int Sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=BIT[i];
    return res;
}
void CDQ(int l,int r){
    if(l>=r) return ;
    int mid=l+r>>1,top1=0,top2=0,j=0;
    CDQ(l,mid);CDQ(mid+1,r);
    for(int i=l;i<=mid;i++) if(!q[i].id) s1[top1++]=q[i];
    for(int i=mid+1;i<=r;i++) if(q[i].id) s2[top2++]=q[i];
    sort(s1,s1+top1);sort(s2,s2+top2);
    //相当于把y1-y2压成一条直线，这样相当于区间[x1,x2],用一维bit维护即可 
    for(int i=0;i<top2;i++){
        for(;j<top1&&s1[j].y<=s2[i].y;j++)
            updata(s1[j].x1,s1[j].f);
        ans[s2[i].id]+=s2[i].f*Sum(s2[i].x2);
        ans[s2[i].id]-=s2[i].f*Sum(s2[i].x1-1);
    }
    for(int i=0;i<j;i++) updata(s1[i].x1,-s1[i].f);
}
int main(){
    freopen("mokia.in","r",stdin);
    freopen("mokia.out","w",stdout);
    int opt=read(),n=read();
    for(int x1,y1,x2,y2,v;(opt=read())!=3;){
        if(opt&1){
            x1=read();y1=read();v=read();
            q[++m]=node(x1,x1,y1,v,0);a[m]=x1;
        }
        else{
            x1=read();y1=read();
            x2=read();y2=read();
            q[++m]=node(x1,x2,y2,1,++id_cnt);a[m]=x2;
            q[++m]=node(x1,x2,y1-1,-1,id_cnt);a[m]=x1-1;
        }
    }
    sort(a+1,a+m+1);
    cnt=unique(a+1,a+m+1)-(a+1);
    for(int i=1;i<=m;i++){
        if(!q[i].id) q[i].x1=hash(q[i].x1);
        else q[i].x1=hash(q[i].x1-1)+1,q[i].x2=hash(q[i].x2);
    }
    CDQ(1,m);
    for(int i=1;i<=id_cnt;i++) printf("%d
",ans[i]);
    return 0;
}

UPD.2017-05-05

#include<cstdio>
#include<cstring>
#include<iostream>
#define lowbit(x) (x&-x)
using namespace std;
inline void read(int &x){
    register char ch=getchar();x=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
}
const int N=2e5+5;
struct query{
    int x,y,d,id;
    query(){}
    query(int _x,int _y,int _d){
        x=_x,y=_y,d=_d;
    }
}q[N],a[N];int m,n,ans[N];
struct BIT{
    int c[(int)2e6+5];
    inline void clr(){memset(c,0,sizeof c);}
    inline void plus(int &p,int v){
        for(int i=p;i<=n;i+=lowbit(i)) c[i]+=v;
    }
    inline int qsum(int &p){
        int res=0;
        for(int i=p;i;i-=lowbit(i)) res+=c[i];
        return res;
    }
}bit;
bool operator <(const query &a,const query &b){
    return a.x!=b.x?a.x<b.x:
           a.y!=b.y?a.y<b.y:
           a.d>b.d;
}
void CDQ(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    int p0=l,p1=mid+1;
    for(int i=l;i<=r;i++){
        a[i]=q[(p1>r||p0<=mid&&q[p0]<q[p1]?p0:p1)++];
        if(a[i].d&&a[i].id<=mid) bit.plus(a[i].y,a[i].d);
        if(!a[i].d&&a[i].id>mid) ans[a[i].id]+=bit.qsum(a[i].y);
    }
    for(int i=l;i<=r;i++){
        if(a[i].d&&a[i].id<=mid) bit.plus(a[i].y,-a[i].d);
        q[i]=a[i];
    }
}
int main(){
    freopen("mokia.in","r",stdin);
    freopen("mokia.out","w",stdout);
    read(n);read(n);
    for(int op,x,y,x0,y0;read(op),op<3;){
        read(x);read(y);read(x0);
        if(op&1){
            q[++m]=query(x,y,x0);
            ans[m]=-1;
        }
        else{
            read(y0);
            q[++m]=query(x0,y0,0);
            q[++m]=query(x-1,y0,0);
            q[++m]=query(x0,y-1,0);
            q[++m]=query(x-1,y-1,0);
        }
    }
    for(int i=1;i<=m;i++) q[i].id=i;
    CDQ(1,m);
    for(int i=1;i<=m;i++) if(~ans[i]){
        printf("%d
",ans[i]-ans[i+1]-ans[i+2]+ans[i+3]);i+=3;
    }
    return 0;
}