Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 1071 Solved: 428
Description
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
|
命令 |
参数限制 |
内容 |
|
1 x y A |
1<=x,y<=N，A是正整数 |
将格子x,y里的数字加上A |
|
2 x1 y1 x2 y2 |
1<=x1<= x2<=N 1<=y1<= y2<=N |
输出x1 y1 x2 y2这个矩形内的数字和 |
|
3 |
无 |
终止程序 |
Input
输入文件第一行一个正整数N。
接下来每行一个操作。
Output
对于每个2操作，输出一个对应的答案。
Sample Input
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
1<=N<=500000,操作数不超过200000个，内存限制20M。
对于100%的数据，操作1中的A不超过2000。
Source
嘛，真是简单题啊，才调了两天就过了。
K-Dtree定期重构，强行维护数据。常数写不好的话会T飞。
之前把47行的左右边界取错了，时间复杂度直接突破天际。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
;
LL read(){
LL x=,f=;char ch=getchar();
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
struct node{
int l,r;
],max[];
];
int w;
LL sum;
}t[mxn];
,nowD;
int cmp(const node a,const node b){
return a.d[nowD]<b.d[nowD];
}
int n,cnt;
;
inline void pushup(int rt,int x){
t[rt].max[]=max(t[rt].max[],t[x].max[]);
t[rt].max[]=max(t[rt].max[],t[x].max[]);
t[rt].min[]=min(t[rt].min[],t[x].min[]);
t[rt].min[]=min(t[rt].min[],t[x].min[]);
return;
}
inline bool in(int x1,int y1,int x2,int y2,int k){
] && t[k].max[]<=x2 &&
y1<=t[k].min[] && t[k].max[]<=y2);
}
inline bool out(int x1,int y1,int x2,int y2,int k){
] || x2<t[k].min[] || y1>t[k].max[] || y2<t[k].min[]);
}
int Build(int l,int r,int D){
;
nowD=D;;
nth_element(t+l,t+mid,t+r+,cmp);///
t[mid].max[]=t[mid].min[]=t[mid].d[];
t[mid].max[]=t[mid].min[]=t[mid].d[];
t[mid].sum=t[mid].w;
t[mid].l=Build(l,mid-,D^);
if(t[mid].l)pushup(mid,t[mid].l);
t[mid].r=Build(mid+,r,D^);
if(t[mid].r)pushup(mid,t[mid].r);
t[mid].sum=t[mid].w+t[t[mid].l].sum+t[t[mid].r].sum;
return mid;
}
void insert(int &now,int x,int D){
if(!now){now=x;return;}
if(t[x].d[D]==t[now].d[D] && t[x].d[!D]==t[now].d[!D]){
t[now].w+=t[x].w;
t[now].sum+=t[x].w;
--cnt;
return;
}
if(t[x].d[D]<t[now].d[D]){
insert(t[now].l,x,D^);
pushup(now,t[now].l);
}
else{
insert(t[now].r,x,D^);
pushup(now,t[now].r);
}
t[now].sum=t[now].w+t[t[now].l].sum+t[t[now].r].sum;
return;
}
LL query(int rt,int x1,int y1,int x2,int y2){
;
LL res=;
if(in(x1,y1,x2,y2,rt)){return t[rt].sum;}
;}
] && t[rt].d[]<=x2 &&
y1<=t[rt].d[] && t[rt].d[]<=y2) res+=t[rt].w;
res+=query(t[rt].l,x1,y1,x2,y2)+query(t[rt].r,x1,y1,x2,y2);
return res;
}
int main(){
int i,j,op,x,y,w;
n=read();lim=;
int X1,X2,Y1,Y2;
){
op=read();
)break;
){
t[++cnt].d[]=read();t[cnt].d[]=read();
t[cnt].w=read();t[cnt].sum=t[cnt].w;
t[cnt].max[]=t[cnt].min[]=t[cnt].d[];
t[cnt].max[]=t[cnt].min[]=t[cnt].d[];
insert(root,cnt,);
if(cnt==lim){
lim+=;
root=Build(,cnt,);
}
}
else{
X1=read();Y1=read();X2=read();Y2=read();
printf("%lld\n",query(root,X1,Y1,X2,Y2));
}
}
;
}