[BZOJ1176][Balkan2007]Mokia

[BZOJ1176][Balkan2007]Mokia

Mokia

Description

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

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

请帮助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      3        查询矩形1<=x<=3,1<=y<=3内的用户数量
1 2 2 2                 向(2,2)方格加入2名用户
2 2 2 3 4      5        查询矩形2<=x<=3,2<=y<=4内的用户数量
3                       终止程序

1<=W<=2000000
1<=X1<=X2<=W
1<=Y1<=Y2<=W
1<=x,y<=W
0

Source

Balkan Olypiad in Informatics 2007,Mokia

只有会员知道的世界……
然后就在COGS上神奇地发现了这道题……
链接:COGS
要是这里能有所有“只有会员知道的世界”系列题该多好啊……

思路:
三维偏序~
不过这题要把询问和修改放在一起分治……

然后在PoPoQQQ大爷那里学到了很好的姿势:
把询问操作的要添加的值一栏设成一个特定的数，只要不和其它添加操作的值冲突就好~
于是咱选了个大质数~(来瞎扯一波:貌似dalao用的是……自己的生日???)
同时把询问拆成二位前缀和的相互加减，共四个前缀和询问~

然后就是三维偏序模板啦~
令三维分别为:(x,y,t)
排序掉x，分治掉t，树状数组对y求逆序对即可~
(事实上对哪一维用什么完全是看心情的~当然写出来的东西也会不一样的啦~)

如果不知道三维偏序的套路可以去看看咱写过的动态逆序对这道题~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>using namespace std;inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}return x*f;
}const int N=200009;
const int M=2002009;
const int qval=19260817;int n;struct node
{int x,y,val,t,ans;node(int _x=0,int _y=0,int _val=0){x=_x;y=_y;val=_val;t=n;ans=0;}
}q[N],tmp[N];inline bool x_cmp(node a,node b){return a.x<b.x;}
inline bool t_cmp(node a,node b){return a.t<b.t;}
inline int lowbit(int x){return x&(-x);}int s,w;
int bit[M],use[M],tim;inline void add(int pos,int val)
{while(pos<=w){if(use[pos]!=tim)bit[pos]=0;use[pos]=tim;bit[pos]+=val;pos+=lowbit(pos);}
}inline int query(int pos)
{int ret=0;while(pos){if(use[pos]==tim)ret+=bit[pos];pos-=lowbit(pos);}return ret;
}void cdq(int l,int r)
{if(l==r)return;int mid=l+r>>1;int ltop=l,rtop=mid+1;for(int i=l;i<=r;i++)if(q[i].t<=mid)tmp[ltop++]=q[i];elsetmp[rtop++]=q[i];memcpy(q+l,tmp+l,sizeof(q[0])*(r-l+1));cdq(l,mid);tim++;ltop=l;for(int i=mid+1;i<=r;i++){for(;q[ltop].x<=q[i].x && ltop<=mid;ltop++)if(q[ltop].val!=qval)add(q[ltop].y,q[ltop].val);if(q[i].val==qval)q[i].ans+=query(q[i].y);}cdq(mid+1,r);ltop=l;rtop=mid+1;for(int i=l;i<=r;i++){if(q[ltop].x<q[rtop].x && ltop<=mid || rtop>r)tmp[i]=q[ltop++];elsetmp[i]=q[rtop++];}memcpy(q+l,tmp+l,sizeof(q[0])*(r-l+1));
}int main()
{if(fopen("mokia.in","r")){freopen("mokia.in","r",stdin);freopen("mokia.out","w",stdout);}s=read();w=read();int op,x1,y1,x2,y2;while((op=read())!=3){if(op==1){x1=read();y1=read();x2=read();q[++n]=node(x1,y1,x2);}else{x1=read();y1=read();x2=read();y2=read();q[++n]=node(x1-1,y1-1,qval);q[++n]=node(x1-1,y2,qval);q[++n]=node(x2,y1-1,qval);q[++n]=node(x2,y2,qval);}}sort(q+1,q+n+1,x_cmp);cdq(1,n);sort(q+1,q+n+1,t_cmp);for(int i=1,ans;i<=n;i++)if(q[i].val==qval){ans=0;ans+=q[i].ans;ans-=q[++i].ans;ans-=q[++i].ans;ans+=q[++i].ans;printf("%dn",ans);}return 0;
}