题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4066

https://www.lydsy.com/JudgeOnline/problem.php?id=2683

高仿:https://www.cnblogs.com/Narh/p/9605505.html

注意细节...

AC 300 ~

代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const xn=2e5+5;
double const alpha=0.75;
int n,cnt,sta[xn],top,rt,dm,c[xn][2],qx1,qx2,qy1,qy2;
int R,fa,son,num;
ll ans;
struct N{
int x[2],y[2],p[2],siz;
ll sum,ys;
}t[xn],a[xn];
int rd()
{
int ret=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return f?ret:-ret;
}
ll Abs(ll x){return x>0?x:-x;}
ll Min(ll x,ll y){return x<y?x:y;}
ll Max(ll x,ll y){return x<y?y:x;}
bool cmp(N x,N y){return x.p[dm]<y.p[dm];}
int node(){if(top)return sta[top--]; else return ++cnt;}
void turn(int x,N v)
{
for(int i=0;i<2;i++)t[x].x[i]=t[x].y[i]=t[x].p[i]=v.p[i];
t[x].ys=t[x].sum=v.ys; t[x].siz=1; c[x][0]=0; c[x][1]=0;//ys //c //v.ys!!!
}
void pushup(int x)
{
int ls=c[x][0],rs=c[x][1];
for(int i=0;i<2;i++)
{
if(ls)t[x].x[i]=Min(t[x].x[i],t[ls].x[i]),t[x].y[i]=Max(t[x].y[i],t[ls].y[i]);
if(rs)t[x].x[i]=Min(t[x].x[i],t[rs].x[i]),t[x].y[i]=Max(t[x].y[i],t[rs].y[i]);
}
t[x].sum=t[x].ys+(ls?t[ls].sum:0)+(rs?t[rs].sum:0);
t[x].siz=1+(ls?t[ls].siz:0)+(rs?t[rs].siz:0);
}
bool ck(int x)
{
int ls=c[x][0],rs=c[x][1];
return (ls&&t[ls].siz>t[x].siz*alpha)||(rs&&t[rs].siz>t[x].siz*alpha);
}
void ins(int &x,N v,int nw)
{
if(!x){x=node(); turn(x,v); return;}
if(v.p[nw]<=t[x].p[nw])ins(c[x][0],v,nw^1);
else ins(c[x][1],v,nw^1);
pushup(x);
if(ck(x))R=x,dm=nw;
if(R==c[x][0])fa=x,son=0; if(R==c[x][1])fa=x,son=1;
}
bool can(int x)
{return t[x].p[0]>=qx1&&t[x].p[0]<=qx2&&t[x].p[1]>=qy1&&t[x].p[1]<=qy2;}
bool in(int x)
{return t[x].x[0]>=qx1&&t[x].y[0]<=qx2&&t[x].x[1]>=qy1&&t[x].y[1]<=qy2;}
bool out(int x)
{return t[x].x[0]>qx2||t[x].y[0]<qx1||t[x].x[1]>qy2||t[x].y[1]<qy1;}
ll query(int x)
{
if(can(x))ans+=t[x].ys;//ys
int ls=c[x][0],rs=c[x][1];
if(ls)
{
if(in(ls))ans+=t[ls].sum;
else if(!out(ls))query(ls);
}
if(rs)
{
if(in(rs))ans+=t[rs].sum;
else if(!out(rs))query(rs);
}
}
void kill(int x)
{
sta[++top]=x; a[++num]=t[x];
if(c[x][0])kill(c[x][0]);
if(c[x][1])kill(c[x][1]);
}
void build(int &x,int l,int r,int nw)
{
x=node(); dm=nw; int mid=((l+r)>>1);
nth_element(a+l,a+mid,a+r+1,cmp);
turn(x,a[mid]);
if(mid>l)build(c[x][0],l,mid-1,nw^1);
if(mid<r)build(c[x][1],mid+1,r,nw^1);
pushup(x);
}
void rbuild(int x)
{
num=0; kill(x); int mid=((1+num)>>1);
nth_element(a+1,a+mid,a+num+1,cmp);
int p=node(); turn(p,a[mid]);
if(fa)c[fa][son]=p; else rt=p;//
if(mid>1)build(c[p][0],1,mid-1,dm^1);
if(mid<num)build(c[p][1],mid+1,num,dm^1);
pushup(p);
}
int main()
{
n=rd(); N tmp;
while((n=rd())!=3)
{
if(n==1)
{
//tmp.p[0]=(rd()^ans); tmp.p[1]=(rd()^ans); tmp.ys=(rd()^ans);
tmp.p[0]=rd(); tmp.p[1]=rd(); tmp.ys=rd();
fa=0; ins(rt,tmp,0);//fa
}
else
{
//qx1=(rd()^ans); qy1=(rd()^ans);
//qx2=(rd()^ans); qy2=(rd()^ans);
qx1=rd(); qy1=rd(); qx2=rd(); qy2=rd();
ans=0; query(rt); printf("%lld\n",ans);
}
if(R){if(R==rt)fa=0; rbuild(R); R=0;}
}
return 0;
}

最新文章

  1. loadrunner录制脚本方式笔记
  2. 让jar程序在linux上一直执行
  3. MyEclipse8.6 破解以及注册码
  4. Java ArrayList操作
  5. mongodb replica set(副本集)设置步骤
  6. Scala学习笔记1(安装)
  7. stack例子
  8. Python模块之ConfigParser - 读写配置文件
  9. LinuxMint(Ubuntu)安装文泉驿家族黑体字
  10. 當 Alexa 遇上 ESP8266 (一)
  11. 洛谷 P3313 [SDOI2014]旅行 解题报告
  12. Java+Jmeter接口测试
  13. 00-自测4. Have Fun with Numbers
  14. c# 产生随机数 程序所在路径
  15. ActiveReports 报表控件V12新特性 -- 文本框和标签控件的浓缩
  16. How Instagram Feeds Work: Celery and RabbitMQ(转)
  17. Spring boot Mybatis整合构建Rest服务(超细版)
  18. Python自定义web框架、Jinja2
  19. Windows Server 2008 R2配置JSP网站无法访问
  20. springmvc 初始化参数绑定(使用属性编辑器) 来处理类型转换问题

热门文章

  1. Netty 100万级到亿级流量 高并发 仿微信 IM后台 开源项目实战
  2. CSS 布局实例系列(二)如何通过 CSS 实现一个左边固定宽度、右边自适应的两列布局
  3. Django 之ModelForm
  4. python-安装 pip
  5. (转)FMS3.5的安装使用及下载地址
  6. python基础1 ---python简介
  7. python SimpleHTTPServer 快速共享文件
  8. cache:annotation-driven&quot; 的前缀 &quot;cache&quot; 未绑定
  9. Data Structure Array: Maximum of all subarrays of size k
  10. STM32 JTDO JREST复用为普通IO