1176: [Balkan2007]Mokia
Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 3381 Solved: 1520
[Submit][Status][Discuss]
Description
维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
Input
第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小
接下来每行为一下三种输入之一(不包含引号):
"1 x y a"
"2 x1 y1 x2 y2"
"3"
输入1:你需要把(x,y)(第x行第y列)的格子权值增加a
输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出
输入3:表示输入结束
Output
对于每个输入2,输出一行,即输入2的答案
Sample Input
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
3
5
5
HINT
题解
首先这个s是假的，把它忽视掉。
天啊，昨天打CDQ分治打得太嗨了，就忘了更新博客了。
说真的，CDQ分治是真的好打，基本上除了开始几道都是1A
这题是个三维偏序裸题。。。
第一维排序，然后第二维CDQ分治，然后以第三维造树状数组。。。
具体看代码。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=;
int s,n,tr[N],cnt,tot,ans[N];
struct query{
int id,k,w,x,y;
bool operator <(const query &a)const{
if(a.id==id){
if(a.x==x){
if(a.y==y){
return a.k>k;
}
else return a.y>y;
}
else return a.x>x;
}
else return a.id>id;
}
}q[N],c[N];
bool pd(query a,query b){
if(a.x==b.x){
if(a.y==b.y){
return a.k<b.k;
}
else return a.y<b.y;
}
else return a.x<b.x;
}
int lowbit(int x){
return x&-x;
}
void add(int x,int w){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=w;
}
}
int getsum(int x){
int ans=;
for(int i=x;i>=;i-=lowbit(i)){
ans+=tr[i];
}
return ans;
}
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>;
cdq(l,mid);cdq(mid+,r);
int ll=l;int rl=mid+;int now=;
while(ll<=mid&&rl<=r){
if(pd(q[ll],q[rl])){
if(q[ll].k==)add(q[ll].y,q[ll].w);
c[++now]=q[ll++];
}
else{
if(q[rl].k==)ans[q[rl].w]-=getsum(q[rl].y);
else if(q[rl].k==)ans[q[rl].w]+=getsum(q[rl].y);
c[++now]=q[rl++];
}
}
while(ll<=mid){
if(q[ll].k==)add(q[ll].y,q[ll].w);
c[++now]=q[ll++];
}
while(rl<=r){
if(q[rl].k==)ans[q[rl].w]-=getsum(q[rl].y);
else if(q[rl].k==)ans[q[rl].w]+=getsum(q[rl].y);
c[++now]=q[rl++];
}
for(int i=l;i<=mid;i++){
if(q[i].k==)add(q[i].y,-q[i].w);
}
for(int i=l;i<=r;i++){
q[i]=c[i-l+];
}
}
int main(){
scanf("%d%d",&s,&n);
n+=;
while(){
int k;
scanf("%d",&k);
if(k==){
int x,y,a;
scanf("%d%d%d",&x,&y,&a);
x+=;y+=;
q[++cnt].x=x;q[cnt].y=y;
q[cnt].id=cnt;q[cnt].k=;
q[cnt].w=a;
}
else if(k==){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1+=;y1+=;x2+=;y2+=;
q[++cnt].x=x2;q[cnt].y=y2;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=++tot;
q[++cnt].x=x1-;q[cnt].y=y2;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=tot;
q[++cnt].x=x2;q[cnt].y=y1-;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=tot;
q[++cnt].x=x1-;q[cnt].y=y1-;q[cnt].id=cnt;q[cnt].k=;q[cnt].w=tot;
}
else break;
}
sort(q+,q++cnt);
// for(int i=1;i<=cnt;i++){
// cout<<q[i].id<<" "<<q[i].x<<" "<<q[i].y<<" "<<q[i].k<<" "<<q[i].w<<endl;;
// }
cdq(,cnt);
for(int i=;i<=tot;i++){
printf("%d\n",ans[i]);
}
return ;
}