1176-->http://qiancl.is-programmer.com/user_files/qiancl/File/Problem%201176.%20--%20[Balkan2007]Mokia.html
4066-->http://www.lydsy.com/JudgeOnline/problem.php?id=4066
以前的坑，今天填了。。三倍经验题好爽啊
裸的k-d tree，注意直接上会T，插若干次重构就行
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return f*x;
}
#define N 200100
struct point{int x,y,v;}q[N];
#define Mx(a,b) (b>a?a=b:a)
#define Mn(a,b) (b<a?a=b:a)
struct KD{
KD*l,*r;int x1,x2,y1,y2,v,sum;point p;
inline void up(KD*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2),sum+=b->sum+b->v;}
inline void set(const point&b){p=b,v=b.v,x1=x2=b.x,y1=y2=b.y;}
}*C[N],Null,*root,*null=&Null;
int i,j,k,n,m,s,x1,y1,ans,x2,y2,x,y,flag,v,cnt,w;bool f;
inline bool cmp(const point&a,const point&b){return f?a.x<b.x||a.x==b.x&&a.y<b.y:a.y<b.y||a.y==b.y&&a.x<b.x;}
inline void insert(KD*root,const point&p){
KD*o=new KD();o->set(p),o->l=o->r=null,f=0;
if(root==null){::root=o;return;}
for(;1;f^=1){
if(p.x==root->p.x&&p.y==root->p.y){root->v+=p.v;return;}root->up(o);
if(cmp(o->p,root->p))if(root->l==null){root->l=o;break;}else root=root->l;
else if(root->r==null){root->r=o;break;}else root=root->r;
}
}
KD *build(int l,int r,int d){
if(l>r)return null;int m=l+r>>1;f=d;
nth_element(q+l+1,q+m+1,q+r+1,cmp);
delete C[w],C[w]=new KD();KD*o=C[w++];o->set(q[m]);
o->l=build(l,m-1,d^1),o->r=build(m+1,r,d^1);
if(o->l!=null)o->up(o->l);if(o->r!=null)o->up(o->r);
return o;
}
void dfs(KD*o){if(o==null)return;dfs(o->l),q[++cnt]=(point){o->p.x,o->p.y,o->v},dfs(o->r);}
inline void rebuild(KD*o){cnt=0,dfs(o),w=0,root=build(1,cnt,0);}
int ask(KD*o,int x1,int y1,int x2,int y2){
if(o==null)return 0;
if(o->x1>=x1&&o->y1>=y1&&o->x2<=x2&&o->y2<=y2)return o->v+o->sum;
int ans=0;
if(o->p.x>=x1&&o->p.x<=x2&&o->p.y>=y1&&o->p.y<=y2)ans+=o->v;
if(!(o->l->x1>x2||o->l->x2<x1||o->l->y1>y2||o->l->y2<y1))ans+=ask(o->l,x1,y1,x2,y2);
if(!(o->r->x1>x2||o->r->x2<x1||o->r->y1>y2||o->r->y2<y1))ans+=ask(o->r,x1,y1,x2,y2);
return ans;
}
int main(){
s=read(),n=read(),root=null;
while(1){
if((flag=read())==3)return 0;
if(flag==1){
x=read(),y=read(),v=read();
insert(root,(point){x,y,v}),++m;
if(m==15000)rebuild(root),m=0;
}else{
x1=read(),y1=read(),x2=read(),y2=read();
printf("%d\n",ask(root,x1,y1,x2,y2)+s*(x2-x1+1)*(y2-y1+1));
}
}
}
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return f*x;
}
struct point{int x,y,v;};
#define N 200100
#define Mx(a,b) (b>a?a=b:a)
#define Mn(a,b) (b<a?a=b:a)
struct KD{
KD*l,*r;int x1,x2,y1,y2,v,sum;point p;
inline void up(KD*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2),sum+=b->sum+b->v;}
inline void set(const point&b){p=b,v=b.v,x1=x2=b.x,y1=y2=b.y;}
}*q[N],Null,*root,*null=&Null;
int i,j,k,n,m,x1,y1,x2,y2,x,y,flag,v,cnt;bool f;
inline bool cmp(const point&a,const point&b){return f?a.x<b.x||a.x==b.x&&a.y<b.y:a.y<b.y||a.y==b.y&&a.x<b.x;}
inline bool cmp1(KD*a,KD*b){return f?a->p.x<b->p.x||a->p.x==b->p.x&&a->p.y<b->p.y:a->p.y<b->p.y||a->p.y==b->p.y&&a->p.x<b->p.x;}
inline void insert(KD*root,const point&p){
KD*o=new KD();o->set(p),o->l=o->r=null,f=0;
if(root==null){::root=o;return;}
for(;1;f^=1){
if(p.x==root->p.x&&p.y==root->p.y){root->v+=p.v;return;}root->up(o);
if(cmp(o->p,root->p))if(root->l==null){root->l=o;break;}else root=root->l;
else if(root->r==null){root->r=o;break;}else root=root->r;
}
}
int ask(KD*o,int x1,int y1,int x2,int y2){
if(o==null)return 0;
if(o->x1>=x1&&o->y1>=y1&&o->x2<=x2&&o->y2<=y2)return o->v+o->sum;
int ans=0;
if(o->p.x>=x1&&o->p.x<=x2&&o->p.y>=y1&&o->p.y<=y2)ans+=o->v;
if(!(o->l->x1>x2||o->l->x2<x1||o->l->y1>y2||o->l->y2<y1))ans+=ask(o->l,x1,y1,x2,y2);
if(!(o->r->x1>x2||o->r->x2<x1||o->r->y1>y2||o->r->y2<y1))ans+=ask(o->r,x1,y1,x2,y2);
return ans;
}
int main(){
n=read(),root=null;
while(1){
if((flag=read())==3)return 0;
if(flag==1){
x=read(),y=read(),v=read();
insert(root,(point){x,y,v});
}else{
x1=read(),y1=read(),x2=read(),y2=read();
printf("%d\n",ask(root,x1,y1,x2,y2));
}
}
}
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return f*x;
}
#define N 200100
struct point{int x,y,v;}q[N];
#define Mx(a,b) (b>a?a=b:a)
#define Mn(a,b) (b<a?a=b:a)
struct KD{
KD*l,*r;int x1,x2,y1,y2,v,sum;point p;
inline void up(KD*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2),sum+=b->sum+b->v;}
inline void set(const point&b){p=b,v=b.v,x1=x2=b.x,y1=y2=b.y;}
}*C[N],Null,*root,*null=&Null;
int i,j,k,n,m,x1,y1,ans,x2,y2,x,y,flag,v,cnt,w;bool f;
inline bool cmp(const point&a,const point&b){return f?a.x<b.x||a.x==b.x&&a.y<b.y:a.y<b.y||a.y==b.y&&a.x<b.x;}
inline void insert(KD*root,const point&p){
KD*o=new KD();o->set(p),o->l=o->r=null,f=0;
if(root==null){::root=o;return;}
for(;1;f^=1){
if(p.x==root->p.x&&p.y==root->p.y){root->v+=p.v;return;}root->up(o);
if(cmp(o->p,root->p))if(root->l==null){root->l=o;break;}else root=root->l;
else if(root->r==null){root->r=o;break;}else root=root->r;
}
}
KD *build(int l,int r,int d){
if(l>r)return null;int m=l+r>>1;f=d;
nth_element(q+l+1,q+m+1,q+r+1,cmp);
delete C[w],C[w]=new KD();KD*o=C[w++];o->set(q[m]);
o->l=build(l,m-1,d^1),o->r=build(m+1,r,d^1);
if(o->l!=null)o->up(o->l);if(o->r!=null)o->up(o->r);
return o;
}
void dfs(KD*o){if(o==null)return;dfs(o->l),q[++cnt]=(point){o->p.x,o->p.y,o->v},dfs(o->r);}
inline void rebuild(KD*o){cnt=0,dfs(o),w=0,root=build(1,cnt,0);}
int ask(KD*o,int x1,int y1,int x2,int y2){
if(o==null)return 0;
if(o->x1>=x1&&o->y1>=y1&&o->x2<=x2&&o->y2<=y2)return o->v+o->sum;
int ans=0;
if(o->p.x>=x1&&o->p.x<=x2&&o->p.y>=y1&&o->p.y<=y2)ans+=o->v;
if(!(o->l->x1>x2||o->l->x2<x1||o->l->y1>y2||o->l->y2<y1))ans+=ask(o->l,x1,y1,x2,y2);
if(!(o->r->x1>x2||o->r->x2<x1||o->r->y1>y2||o->r->y2<y1))ans+=ask(o->r,x1,y1,x2,y2);
return ans;
}
int main(){
n=read(),root=null;
while(1){
if((flag=read())==3)return 0;
if(flag==1){
x=read()^ans,y=read()^ans,v=read()^ans;
insert(root,(point){x,y,v}),++m;
if(m==16000)rebuild(root),m=0;
}else{
x1=read()^ans,y1=read()^ans,x2=read()^ans,y2=read()^ans;
printf("%d\n",ans=ask(root,x1,y1,x2,y2));
}
}
}
loading...
评论 (0)
