COGS1752. [BOI2007]摩基亚Mokia(CDQ,树状数组)

题目描述

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

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

COGS1752. [BOI2007]摩基亚Mokia(CDQ,树状数组)

请帮助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: 复制
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
输出样例#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个。

题解

树状数组没有清空结果调了几个小时……快疯了……

坐标范围太大,先考虑离散

我们把一个操作看成$(a,x,y)$的形式,其中$a$代表时间,$x,y$代表坐标(查询操作可以通过差分拆成四个操作)

然后就是一个三维偏序问题了,用CDQ+树状数组解决

时间这一维是默认有序的

$x$这一维可以用CDQ自带的归并排好序

$y$这一维用树状数组就可以求出答案

 //minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=;
struct node{
int x,y,d,id;
inline void add(int a,int b,int c,int _id=)
{x=a,y=b,d=c,id=_id;}
inline bool operator <(const node &b)const{
return x!=b.x?x<b.x:
y!=b.y?y<b.y:
d>b.d;
}
}a[N],p[N];int n,m,ans[N];
int c[N*];
inline void add(int x,int val){
for(int i=x;i<=n;i+=i&(-i))
c[i]+=val;
}
inline int query(int x){
int res=;
for(int i=x;i;i-=i&(-i))
res+=c[i];
return res;
}
inline void clear(int x){
for(int i=x;i<=n;i+=i&(-i))
if(c[i]) c[i]=;
else return;
}
void cdq(int l,int r){
if(l==r) return;
int mid=(l+r)>>;
cdq(l,mid),cdq(mid+,r);
int i=l,j=l,k=mid+;
while(j<=mid&&k<=r){
if(p[j]<p[k]){
if(p[j].d) add(p[j].y,p[j].d);
a[i++]=p[j++];
}
else{
if(!p[k].d) ans[p[k].id]+=query(p[k].y);
a[i++]=p[k++];
}
}
while(j<=mid) a[i++]=p[j++];
while(k<=r){
if(!p[k].d) ans[p[k].id]+=query(p[k].y);
a[i++]=p[k++];
}
for(int i=l;i<=r;++i){
clear(a[i].y);p[i]=a[i];
}
}
int main(){
//freopen("testdata.in","r",stdin);
n=read(),n=read();
for(int x,y,xx,yy,opt;(opt=read())!=;){
x=read(),y=read(),xx=read();
if(opt&){
p[++m].add(x,y,xx,m+);
ans[m]=-;
}
else{
yy=read();
p[++m].add(xx,yy,,m+),p[++m].add(x-,yy,,m+);
p[++m].add(xx,y-,,m+),p[++m].add(x-,y-,,m+);
}
}
cdq(,m);
for(int i=;i<=m;++i)
if(~ans[i]){
int k=ans[i]-ans[i+]-ans[i+]+ans[i+];
print(k);i+=;
}
Ot();
return ;
}
上一篇:MetaSploit Pro 下载地址


下一篇:PRML读书会第八章 Graphical Models(贝叶斯网络,马尔科夫随机场)