摩基亚Mokia

P1948 - 【BOI2007】摩基亚Mokia

Description

摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户C的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。
在定位系统中，世界被认为是一个W * W的正方形区域，由1 * 1的方格组成。每个方格都有一个坐标(x,y)，1<=x,y<=W。坐标的编号从1开始。对于一个4 * 4的正方形，就有1<=x<=4,1<=y<=4（如图）：

摩基亚Mokia

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

Input

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

Output

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

Sample Input

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

Sample Output

3
5

Hint

样例提示：
输入输出意义
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个。

Source

Balkan Olypiad in Informatics 2007,Mokia
陈丹琦分治，分治，树状数组

Accepted entrance

CDQ分治，把一个矩阵的询问拆成四个，运用容斥原理，给每个询问一个时间顺序。可以发现，修改只是单个格子修改，只有修改的这个各自的横坐标小于询问的横坐标，才会对这个询问产生贡献，刚好是三维的（x,y,time），于是time排序，xCDQ分治，y树状数组维护，还是一个样的，计算左区间[l,mid]对右区间[mid+1,r]的贡献，统计答案。

参考博客:http://wulala.logdown.com/posts/207262-boi-2007-mokia

 1 #define ll long long
 2 #define rep(i,a,b) for(int i=a;i<=b;i++)
 3 #define lowbit(p) p & (-p)
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<iomanip>
 7 #include<cstring>
 8 #include<cstdlib>
 9 #include<cstdio>
10 #include<queue>
11 #include<ctime>
12 #include<cmath>
13 #include<stack>
14 #include<map>
15 #include<set>
16 using namespace std;
17 const int N=160010*4+10000;
18 int tot,W,C[2000000+10],q;
19 struct Q{
20     int x,y,k,q,v,od;//  k 种类  q Index_ans   v val or -+   id _ time
21 }que[N],np[N];
22 int Ans[N];
23 bool comp(const Q &a,const Q &b) {
24     return a.x<b.x;
25 }
26 void add(int p,int x) {
27     if(!p) return;
28     while(p<=W) C[p]+=x,p+=lowbit(p);
29 }
30 int getsum(int p) {
31     int sum=0;
32     while(p) sum+=C[p],p-=lowbit(p);
33     return sum;
34 }
35 int gi() {
36     int res=0,f=1;
37     char ch=getchar();
38     while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
39     if(ch=='-') ch=getchar(),f=-1;
40     while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
41     return res*f;
42 }
43 void CDQ(int l,int r)  {
44     if(l==r) return;
45     int mid=(l+r)>>1;
46     int l1=l,l2=mid+1;
47     rep(i,l,r) if(que[i].od<=mid) np[l1++]=que[i];else np[l2++]=que[i];
48     rep(i,l,r) que[i]=np[i];
49     l1=l;
50     rep(i,mid+1,r) if(que[i].k==2){
51     for(;l1<=mid&&que[l1].x<=que[i].x;l1++) {
52         if(que[l1].k==1)
53         add(que[l1].y,que[l1].v);
54     }
55     Ans[que[i].q]+=getsum(que[i].y)*que[i].v;    
56     }
57     rep(i,l,l1-1) if(que[i].k==1) add(que[i].y,-que[i].v);
58     CDQ(l,mid) , CDQ(mid+1,r);
59 }
60 void work() {
61     while(1) {
62     int Type=gi(),x,y;
63     if(Type==3) break;
64     if(Type==1) {
65         x=gi(),y=gi();int c=gi();
66         que[++tot]=(Q){x,y,1,0,c,tot};
67     }
68     else {
69         ++q;
70         x=gi(),y=gi();int u2=gi(),v2=gi();
71         que[++tot]=(Q){x-1,y-1,2,q,1,tot};
72         que[++tot]=(Q){x-1,v2,2,q,-1,tot};
73         que[++tot]=(Q){u2,y-1,2,q,-1,tot};// y-1 v2-1
74         que[++tot]=(Q){u2,v2,2,q,1,tot};
75     }
76     }
77   
78     sort(que+1,que+tot+1,comp);
79     CDQ(1,tot);
80     return;
81 }
82 int main() {
83         freopen("mokia.in","r",stdin);
84         freopen("mokia.out","w",stdout);
85     
86     int Type=gi();
87     W=gi();
88     work();
89     rep(i,1,q) printf("%d
",Ans[i]);
90     return 0;
91 }

View Code