同p1176。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 200011
#define KD 2//ά¶ÈÊý
int qp[2][2];
int n,root=1,m;
bool dn;
struct Node
{
int minn[KD],maxx[KD],p[KD],w,ch[2],sumv;
void Init()
{
for(int i=0;i<KD;++i)
minn[i]=maxx[i]=p[i];
sumv=w;
}
}T[N];
void Clear()
{
for(int i=1;i<=n;++i)
T[i].ch[0]=T[i].ch[1]=/*T[i].sumv=T[i].minn[0]=T[i].minn[1]=T[i].maxx[0]=T[i].maxx[1]=*/0;
}
void Update(int rt)
{
T[rt].sumv=T[rt].w;
for(int i=0;i<2;++i)
if(T[rt].ch[i])
{
T[rt].sumv+=T[T[rt].ch[i]].sumv;
for(int j=0;j<KD;++j)
{
T[rt].minn[j]=min(T[rt].minn[j],T[T[rt].ch[i]].minn[j]);
T[rt].maxx[j]=max(T[rt].maxx[j],T[T[rt].ch[i]].maxx[j]);
}
}
}
bool operator < (const Node &a,const Node &b){return a.p[dn]<b.p[dn];}
int Buildtree(int l=1,int r=n,bool d=0)
{
dn=d;
int m=(l+r>>1);
nth_element(T+l,T+m,T+r+1);
T[m].Init();
if(l!=m) T[m].ch[0]=Buildtree(l,m-1,d^1);
if(m!=r) T[m].ch[1]=Buildtree(m+1,r,d^1);
Update(m);
return m;
}
void Insert(int rt=root,bool d=0)
{
bool f=(T[n].p[d]>T[rt].p[d]);
if(T[rt].ch[f]) Insert(T[rt].ch[f],d^1);
else T[rt].ch[f]=n;
Update(rt);
}
int ans;
void Query(int rt=root)
{
if(T[rt].p[0] >= qp[0][0] && T[rt].p[0] <= qp[1][0]
&& T[rt].p[1] >= qp[0][1] && T[rt].p[1] <= qp[1][1])
ans+=T[rt].w;
for(int i=0;i<2;++i)
if(T[rt].ch[i]
&& T[T[rt].ch[i]].maxx[0] >= qp[0][0] && T[T[rt].ch[i]].minn[0] <= qp[1][0]
&& T[T[rt].ch[i]].maxx[1] >= qp[0][1] && T[T[rt].ch[i]].minn[1] <= qp[1][1])
{
if(T[T[rt].ch[i]].minn[0] >= qp[0][0] && T[T[rt].ch[i]].maxx[0] <= qp[1][0]
&& T[T[rt].ch[i]].minn[1] >= qp[0][1] && T[T[rt].ch[i]].maxx[1] <= qp[1][1])
ans+=T[T[rt].ch[i]].sumv;
else
Query(T[rt].ch[i]);
}
}
int op[N],X1[N],Y1[N],X2[N],Y2[N],Vs[N];
int main()
{
// freopen("bzoj4066.in","r",stdin);
// freopen("bzoj4066.out","w",stdout);
// for(int i=1;i<=1000000;++i);
scanf("%d",&m); m=0;
while(1)
{
++m;
scanf("%d",&op[m]);
if(op[m]==3)
{
--m;
break;
}
if(op[m]==1)
{
scanf("%d%d%d",&X1[m],&Y1[m],&Vs[m]);
++n;
}
else
scanf("%d%d%d%d",&X1[m],&Y1[m],&X2[m],&Y2[m]);
}
int blo=(int)sqrt((double)n*log2((double)n));
n=0;
for(int i=1;i<=m;++i)
{
if(op[i]==1)
{
++n;
T[n].p[0]=X1[i]; T[n].p[0]^=ans;
T[n].p[1]=Y1[i]; T[n].p[1]^=ans;
T[n].w=Vs[i]; T[n].w^=ans;
// printf("Insert%d:(%d,%d):%d\n",n,T[n].p[0],T[n].p[1],T[n].w);
T[n].Init();
if(n>1)
Insert();
if(blo==1 || blo==0 || n%blo==0)
{
Clear();
Buildtree();
root=(1+n>>1);
}
}
else
{
qp[0][0]=X1[i]; qp[0][0]^=ans;
qp[0][1]=Y1[i]; qp[0][1]^=ans;
qp[1][0]=X2[i]; qp[1][0]^=ans;
qp[1][1]=Y2[i]; qp[1][1]^=ans;
ans=0;
if(n)
Query();
printf("%d\n",ans);
}
}
}

最新文章

  1. Java 教程整理:基础、项目全都有
  2. ActiveMQ实现负载均衡+高可用部署方案
  3. 基本套接字编程(7) -- udp篇
  4. 被废了的display:box弹性盒模型
  5. 工作中常用的Linux命令:mkdir命令
  6. mac10.9+php5.5.15+brew0.9.5的安装
  7. Python自动化 【第三篇】:Python基础-集合、文件操作、字符编码与转码、函数
  8. Sql server之路 (三)添加本地数据库SDF文件
  9. Learning Vector
  10. ACM大数模板(支持正负整数)
  11. Java的λ表达(lambda)
  12. 用css制作一个三角形箭头
  13. python网络编程之单线程之间的并发
  14. Nginx负载均衡搭建(Window与Linux)
  15. Gitlab管理网页老是500错误?增加物理内存,增加cpu吧
  16. laravel compact的用法
  17. iOS快捷代码块
  18. 20165319 《JAVA程序设计》第一周学习总结
  19. ubuntu18.04 安装mysql server
  20. 实现AJAX的基本步骤

热门文章

  1. 闲话JavaScript与Cookies
  2. codeforces 719C. Efim and Strange Grade
  3. remove computer from join with powershell
  4. [01]url请求到渲染
  5. mavne问题解决---Dynamic Web Module 2.3 or newer
  6. 动态规划:树形DP
  7. codeforces613B - Skills &amp;&amp;金中市队儿童节常数赛
  8. 【BZOJ】1799: [Ahoi2009]self 同类分布
  9. javascript学习3
  10. Symfony2之创建一个简单的web应用 Symfony2——创建bundle