BZOJ2648: SJY摆棋子&&2716: [Violet 3]天使玩偶
2024-08-25 14:41:34
BZOJ氪金无极限。。。
其实这两道是同一题。
附上2648的题面:
Description
这天,SJY显得无聊。在家自己玩。
在一个棋盘上,有N个黑色棋子。
他每次要么放到棋盘上一个黑色棋子,要么放上一个白色棋子,如果是白色棋子,他会找出距离这个白色棋子最近的黑色棋子。
此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。
现在给出N<=500000个初始棋子。和M<=500000个操作。
对于每个白色棋子,输出距离这个白色棋子最近的黑色棋子的距离。
同一个格子可能有多个棋子。
Input
第一行两个数 N M
以后M行,每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子
Output
对于每个T=2 输出一个最小距离
Sample Input
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2
1 1
2 3
2 1 2
1 3 3
2 4 2
Sample Output
1
2
2
题解Here!
没有插入操作,就无脑$K-D\ Tree$即可。
有了插入操作怎么办呢?
我们可以类比于平衡树,查找要插入的点应该在什么位置。
然后插入就好。
但是很容易就会发现这玩意会形成一条链。
复杂度笋干爆炸。。。
怎么办呢?
$K-D\ Tree$一大缺点就是建好的树不能再动。
暴力重建?
复杂度依然$GG$。。。
等一下!不能每次都暴力重建,那我就偶尔几次暴力重建就是了?
对,这种方法已经被成功运用到替罪羊树中。
设$\alpha=0.75$,当前在$x$处。
假如$x$的左右子树中有一颗子树的大小$>x\text{的子树大小}\times\alpha$,说明该子树已经极其不平衡。
我们需要对其进行暴力拍平重建。
拍平代码的话,大概长这个样子:
void pia(int rt,int num){
if(a[rt].lson)pia(a[rt].lson,num);
point[num+a[a[rt].lson].size+1]=a[rt].point;
recycle[++top]=rt;
if(a[rt].rson)pia(a[rt].rson,num+a[a[rt].lson].size+1);
}
重建的话,和最开始的建树过程相同。
这样,插入操作就解决了。
期望复杂度$O(\text{能过})$。
附代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 1000010
#define MAX (1LL<<30)
#define Alpha 0.75
using namespace std;
int n,m,root,ans,size=0;
int top=0,recycle[MAXN];
bool sort_flag=false;
struct Point{
int x,y;
friend bool operator <(const Point &p,const Point &q){
if(sort_flag)return p.y<q.y;
return p.x<q.x;
}
}point[MAXN],now;
struct Tree{
Point point;
int minx,miny,maxx,maxy,lson,rson,size;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline int get_dis(const Point &p,const Point &q){
return abs(p.x-q.x)+abs(p.y-q.y);
}
inline int newnode(const Point &p){
int rt;
if(top)rt=recycle[top--];
else rt=++size;
a[rt].point=p;
a[rt].maxx=a[rt].minx=p.x;
a[rt].maxy=a[rt].miny=p.y;
a[rt].lson=a[rt].rson=0;
a[rt].size=1;
return rt;
}
inline void pushup(int rt){
int lson=a[rt].lson,rson=a[rt].rson;
a[rt].size=a[lson].size+a[rson].size+1;
a[rt].maxx=max(a[rt].maxx,max(a[lson].maxx,a[rson].maxx));
a[rt].maxy=max(a[rt].maxy,max(a[lson].maxy,a[rson].maxy));
a[rt].minx=min(a[rt].minx,min(a[lson].minx,a[rson].minx));
a[rt].miny=min(a[rt].miny,min(a[lson].miny,a[rson].miny));
}
void buildtree(int l,int r,int &rt,int flag){
int mid=l+r>>1;
sort_flag=flag;
nth_element(point+l,point+mid,point+r+1);
rt=newnode(point[mid]);
if(l<mid)buildtree(l,mid-1,a[rt].lson,flag^1);
if(mid<r)buildtree(mid+1,r,a[rt].rson,flag^1);
pushup(rt);
}
void pia(int rt,int num){
if(a[rt].lson)pia(a[rt].lson,num);
point[num+a[a[rt].lson].size+1]=a[rt].point;
recycle[++top]=rt;
if(a[rt].rson)pia(a[rt].rson,num+a[a[rt].lson].size+1);
}
void check(int &rt,int flag){
if(Alpha*a[rt].size<max(a[a[rt].lson].size,a[a[rt].rson].size)){
pia(rt,0);
buildtree(1,a[rt].size,rt,flag);
}
}
void insert(int &rt,int flag){
if(!rt){
rt=newnode(now);
return;
}
sort_flag=flag;
if(a[rt].point<now)insert(a[rt].rson,flag^1);
else insert(a[rt].lson,flag^1);
pushup(rt);
check(rt,flag);
}
inline int max_dis(int rt){
int x,y;
x=max(now.x-a[rt].maxx,0)+max(a[rt].minx-now.x,0);
y=max(now.y-a[rt].maxy,0)+max(a[rt].miny-now.y,0);
return x+y;
}
void query(int rt){
int dis=get_dis(a[rt].point,now),ldis=MAX,rdis=MAX;
ans=min(ans,dis);
if(a[rt].lson)ldis=max_dis(a[rt].lson);
if(a[rt].rson)rdis=max_dis(a[rt].rson);
if(ldis<rdis){
if(ldis<ans)query(a[rt].lson);
if(rdis<ans)query(a[rt].rson);
}
else{
if(rdis<ans)query(a[rt].rson);
if(ldis<ans)query(a[rt].lson);
}
}
void work(){
int f;
while(m--){
f=read();now.x=read();now.y=read();
if(f==1)insert(root,0);
else{
ans=MAX;
query(root);
printf("%d\n",ans);
}
}
}
void init(){
n=read();m=read();
a[0].maxx=a[0].maxy=-MAX;
a[0].minx=a[0].miny=MAX;
for(int i=1;i<=n;i++){point[i].x=read();point[i].y=read();}
buildtree(1,n,root,0);
}
int main(){
init();
work();
return 0;
}
最新文章
- 解决java.lang.NoClassDefFoundError: org/objectweb/asm/util/TraceClassVisitor
- jquery动态改变div宽度和高度
- pjax技术的应用
- jsp:软件包 javax.servlet 不存在
- 关于swfupload,客户端中文乱码解决方案!
- 我所了解的WEB开发(3) - 彩虹的颜色
- 浅谈负载均衡SLB、CLB和综合应用
- python 拷贝文件夹下所有的文件到指定文件夹(不包括目录)
- openlayers3 在地图上叠加WFS查询矢量图层
- Express 学习记录
- AngularJs学习笔记2——四大特性之MVC
- hdu_5193_Go to movies Ⅱ(带插入删除的逆序对,块状链表)
- windows Vista-Server 2016系列激活脚本.cmd
- 福州大学W班-团队作业-随堂小测(同学录)成绩
- bzoj 2957 楼房重建 (线段树+思路)
- 洛谷P4070 生成魔咒
- Python函数——装饰器
- ssh客户端连接报认证失败
- Python学习笔记第十周
- Java中的方法重载
热门文章
- [k8s]简单启动一个k8s集群
- C++语言基础(23)-拷贝构造函数
- poj 1475 Pushing Boxes 推箱子(双bfs)
- poj Ping pong LA 4329 (树状数组统计数目)
- java虚拟机的逃逸分析
- codeForces 574b Bear and Three Musketeers
- ubuntun 下安装 node-v0.10.26
- 【PM面试题】设计一个股价推送工具
- (转载)【C#4.0】dynamic和var及object
- secureCRT连接不上linux的当中一个最大的原因