bzoj 4066 & bzoj 2683 简单题 —— K-D树(含重构)
2024-08-28 22:43:13
题目: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;
}
最新文章
- loadrunner录制脚本方式笔记
- 让jar程序在linux上一直执行
- MyEclipse8.6 破解以及注册码
- Java ArrayList操作
- mongodb replica set(副本集)设置步骤
- Scala学习笔记1(安装)
- stack例子
- Python模块之ConfigParser - 读写配置文件
- LinuxMint(Ubuntu)安装文泉驿家族黑体字
- 當 Alexa 遇上 ESP8266 (一)
- 洛谷 P3313 [SDOI2014]旅行 解题报告
- Java+Jmeter接口测试
- 00-自测4. Have Fun with Numbers
- c# 产生随机数 程序所在路径
- ActiveReports 报表控件V12新特性 -- 文本框和标签控件的浓缩
- How Instagram Feeds Work: Celery and RabbitMQ(转)
- Spring boot Mybatis整合构建Rest服务(超细版)
- Python自定义web框架、Jinja2
- Windows Server 2008 R2配置JSP网站无法访问
- springmvc 初始化参数绑定(使用属性编辑器) 来处理类型转换问题
热门文章
- Netty 100万级到亿级流量 高并发 仿微信 IM后台 开源项目实战
- CSS 布局实例系列(二)如何通过 CSS 实现一个左边固定宽度、右边自适应的两列布局
- Django 之ModelForm
- python-安装 pip
- (转)FMS3.5的安装使用及下载地址
- python基础1 ---python简介
- python SimpleHTTPServer 快速共享文件
- cache:annotation-driven"; 的前缀 ";cache"; 未绑定
- Data Structure Array: Maximum of all subarrays of size k
- STM32 JTDO JREST复用为普通IO