P4390 [BOI2007]Mokia 摩基亚
题目描述
摩尔瓦多的移动电话公司摩基亚（(Mokia)）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户(C)的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。
在定位系统中，世界被认为是一个(W imes W)的正方形区域，由(1 imes1)的方格组成。每个方格都有一个坐标((x,y))，(1le x,yle W)。坐标的编号从(1)开始。对于一个(4 imes4)的正方形，就有(1le xle 4,1le yle 4)（如图）：
请帮助(Mokia)公司编写一个程序来计算在某个矩形区域内有多少名用户。
输入输出格式
输入格式：
有三种命令，意义如下：
命令 参数 意义
0 W初始化一个全零矩阵。本命令仅开始时出现一次。1 x y A向方格((x,y))中添加(A)个用户。(A)是正整数。2 X1 Y1 X2 Y2查询(X_1le xle X_2,Y_1le yle Y_2)所规定的矩形中的用户数量3无参数 结束程序。本命令仅结束时出现一次。
输出格式：
对所有命令(2)，输出一个一行整数，即当前询问矩形内的用户数量。
说明
对于所有数据：
(1le Wle 2000000)
(1le X_1le X_2le W)
(1le Y_1le Y_2le W)
(1le x,yle W)
(0<Ale 10000)
命令(1)不超过(160000)个。
命令(2)不超过(10000)个。
之前做了个园丁的题目，是所有询问在修改之后的。
于是直接把四维偏序的一维搞成区间操作(O(nlog^2n))水过去了。
然后这个题就萎掉了，想了一会儿还是三个(log)，于是打算拿树套树水过去。
结果套的线段树(MLE)了，无语...
然后看了看正解，发现直接对矩形容斥就可以了。
就是把一个矩形((a,b),(c,d))拆成((1,1),(a-1,b-1))、((1,1),(a-1,d))、((1,1),(c,b-1))、((1,1),(c,d))四个做。
然后就又成了三维偏序...
Code:
#include <cstdio>
#include <algorithm>
const int N=2e5+10;
int n,m,k,op,ans[N],s[N<<2],dx[N<<2],cntx,dy[N<<2],cnty;
void add(int x,int d){while(x<=cnty)s[x]+=d,x+=x&-x;}
int ask(int x){int sum=0;while(x)sum+=s[x],x-=x&-x;return sum;}
struct node
{
int a,b,c,op;
bool friend operator <(node n1,node n2)
{
return n1.a==n2.a?n1.op<n2.op:n1.a<n2.a;
}
}q[N],qs[N];
void CDQ(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
CDQ(l,mid),CDQ(mid+1,r);
int lp=l,rp=mid+1,loc=l-1;
while(lp<=mid&&rp<=r)
{
if(q[lp]<q[rp])
{
if(!q[lp].op) add(q[lp].b,q[lp].c);
qs[++loc]=q[lp++];
}
else
{
if(q[rp].op) ans[q[rp].op]+=q[rp].c*ask(q[rp].b);
qs[++loc]=q[rp++];
}
}
while(rp<=r)
{
if(q[rp].op) ans[q[rp].op]+=q[rp].c*ask(q[rp].b);
qs[++loc]=q[rp++];
}
for(int i=l;i<lp;i++) if(!q[i].op) add(q[i].b,-q[i].c);
while(lp<=mid) qs[++loc]=q[lp++];
for(int i=l;i<=r;i++) q[i]=qs[i];
}
int main()
{
scanf("%d%d",&n,&n);
scanf("%d",&op);int a,b,c,d;
while(op!=3)
{
if(op==1)
{
++m;
scanf("%d%d%d",&q[m].a,&q[m].b,&q[m].c);
dx[++cntx]=q[m].a,dy[++cnty]=q[m].b;
}
else
{
scanf("%d%d%d%d",&a,&b,&c,&d);
dx[++cntx]=a-1,dy[++cnty]=b-1,dx[++cntx]=c,dy[++cnty]=d;
++k;
q[++m]={a-1,b-1,1,k};
q[++m]={a-1,d,-1,k};
q[++m]={c,b-1,-1,k};
q[++m]={c,d,1,k};
}
scanf("%d",&op);
}
std::sort(dx+1,dx+1+cntx);
std::sort(dy+1,dy+1+cnty);
cntx=std::unique(dx+1,dx+1+cntx)-dx-1;
cnty=std::unique(dy+1,dy+1+cnty)-dy-1;
for(int i=1;i<=m;i++)
{
q[i].a=std::lower_bound(dx+1,dx+1+cntx,q[i].a)-dx;
q[i].b=std::lower_bound(dy+1,dy+1+cnty,q[i].b)-dy;
}
CDQ(1,m);
for(int i=1;i<=k;i++) printf("%d
",ans[i]);
return 0;
}
2018.11.27