一道毒瘤的 主席树套 $\texttt{k-D Tree}$ 题,或者 暴力分块 的简单题。
题目链接:Luogu P4848/LibreOJ 6016。
题目
题目描述
具体说来,蒟蒻 Bob 会在一个宽敞的广场上放置一些崂山白花蛇草水(可视为二维平面上的一些整点),然后询问神犇 Aleph 在矩形区域 $x_1\leq x\leq x_2,y_1\leq y\leq y_2$ 中,崂山白花蛇草水瓶数第 $k$ 多的是多少。为了避免麻烦,蒟蒻 Bob 不会在同一个位置放置两次或两次以上的崂山白花蛇草水,但蒟蒻 Bob 想为难一下神犇 Aleph,希望他能在每次询问时立刻回答出答案。
神犇 Aleph 不屑于做这种问题,所以把这个问题交给了你。
数据范围
变量 | 数据范围 |
---|---|
坐标范围 | $5\times 10^5$ |
操作次数 | $10^5$ |
$v$ | $10^9$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
Luogu P4848 | $3\text{s}$ | $500\text{MiB}$ |
LibreOJ 6016 | $4\text{s}$ | $512\text{MiB}$ |
题解
本题有多种写法。
写法一
不保证能过的奇怪写法(数据过水)。
暴力分块,开两个数组,一大一小,小的大小约为 $\sqrt{q}+1$。
每次加点往小的数组里面用插入排序的方法加,按 $v$ 排列,超过大小后按照归并排序的方法合并两个数组。
查询时按照归并的方法查询。
期望时间复杂度为 $\Theta(q\sqrt{q}+q^2)$。实际开 O2 优化能过(数据太水了)。
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getcharead()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getcharead();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getcharead();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getcharead();
return f?-res:res;
}
const int MAXQ=100000+5;
struct Querys{
int x,y,v;
inline Querys(reg int x=0,reg int y=0,reg int v=0):x(x),y(y),v(v){
return;
}
};
int n,Q;
Querys big[MAXQ],small[MAXQ];
inline bool in(const Querys& Q,reg int x1,reg int x2,reg int y1,reg int y2){
return x1<=Q.x&&Q.x<=x2&&y1<=Q.y&&Q.y<=y2;
}
int main(void){
n=read(),Q=read();
reg int cnt1=0,cnt2=0;
reg int lastans=0;
reg int BLOCK=sqrt(n)+1;
while(Q--){
static int type;
type=read();
if(type==1){
static int x,y,v;
x=read(),y=read(),v=read();
x^=lastans,y^=lastans,v^=lastans;
reg int ptr=0;
for(ptr=cnt2;ptr&&small[ptr].v>v;--ptr)
small[ptr+1]=small[ptr];
small[ptr+1]=Querys(x,y,v);
++cnt2;
if(cnt2>=BLOCK){
static Querys temp[MAXQ];
reg int i=cnt1,j=cnt2,k=cnt1+cnt2;
while(i&&j){
if(big[i].v>small[j].v)
temp[k--]=big[i--];
else
temp[k--]=small[j--];
}
while(i)
temp[k--]=big[i--];
while(j)
temp[k--]=small[j--];
for(reg int i=1;i<=cnt1+cnt2;++i)
big[i]=temp[i];
cnt1=cnt1+cnt2;
cnt2=0;
}
}
if(type==2){
static int x1,y1,x2,y2,k;
x1=read(),y1=read(),x2=read(),y2=read(),k=read();
x1^=lastans,y1^=lastans,x2^=lastans,y2^=lastans,k^=lastans;
if(k>cnt1+cnt2){
puts("NAIVE!ORZzyz.");
lastans=0;
continue;
}
reg int i=cnt1,j=cnt2;
while(i&&j&&k){
if(big[i].v>small[j].v){
if(in(big[i],x1,x2,y1,y2))
--k;
if(k==0){
printf("%d\n",lastans=big[i].v);
break;
}
--i;
}
else{
if(in(small[j],x1,x2,y1,y2))
--k;
if(k==0){
printf("%d\n",lastans=small[j].v);
break;
}
--j;
}
}
while(i&&k){
if(in(big[i],x1,x2,y1,y2))
--k;
if(k==0){
printf("%d\n",lastans=big[i].v);
break;
}
--i;
}
while(j&&k){
if(in(small[j],x1,x2,y1,y2))
--k;
if(k==0){
printf("%d\n",lastans=small[j].v);
break;
}
--j;
}
if(k){
puts("NAIVE!ORZzyz.");
lastans=0;
}
}
}
return 0;
}
写法二
思路
首先观察到二维平面,考虑使用 $\texttt{k-D Tree}$。
其次观察到第 $k$ 大,考虑 主席树。
于是决定使用 主席树套 $\texttt{k-D Tree}$ 来解决问题。相当于每个结点上开一个 $\texttt{k-D Tree}$。动态插入 + 替罪羊树式重构,查询时可以这么做:
- 确定一个 $t$;
- 求 $v$ 大于等于 $t$ 且在 查询范围内的点的个数 (用 $\texttt{k-D Tree}$);
- 如果个数大于 $k$,增加 $t$,否则减小 $t$。
- 最后得到的 $t$ 就是答案。二分 $t$ 即可,最终的时间复杂度是 $\Theta(q\log_2v\log_2q)$,比较优秀。
代码
代码比较长,并且这道题目时间比较松($3\text{s}$比较长),推荐管理员卡到 $1.5\text{s}$,这道题目也可以卡一卡常数。
卡常数
- 写快读,因为本题数字都是正数(好像没有 $0$),所以不需要考虑符号;
- 不要写快速输出,那个东西慢的很;
- $\texttt{k-D Tree}$ 里面不要用很多数组,要写成结构体的形式,不然很慢;
x=max(x,y)
全部改成cMax(x,y)
这样的形式,其中有宏定义#define cMax(x,y) ( (x) < (y) ? (x) = (y) : (0) )
;开 O2 优化。
下面就是代码了。
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 1e9
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=100000+5;
const double alpha=0.75;
const int MAXSIZE=MAXN*20;
int n,K;
int X[2];
int _Max[2],_Min[2];
namespace SegmentTree{
#define mid ( ( (l) + (r) ) >> 1 )
int lastans;
namespace kD_Tree{
#define cMax(x,y) ( (x) < (y) ? (x) = (y) : (0) )
#define cMin(x,y) ( (x) > (y) ? (x) = (y) : (0) )
int cnt;
#define val(x,y) T[x].val[y]
#define Max(x,y) T[x].Max[y]
#define Min(x,y) T[x].Min[y]
#define lson(x) T[x].lson
#define rson(x) T[x].rson
#define size(x) T[x].size
struct Node{
int size;
int lson,rson;
int Max[2],Min[2];
int val[2];
}T[MAXSIZE];
int WD,p[MAXN];
inline bool cmp(reg int a,reg int b){
return val(a,WD)<val(b,WD);
}
inline void pushup(reg int k){
reg int l=lson(k),r=rson(k);
if(l)
cMax(Max(k,0),Max(l,0)),cMax(Max(k,1),Max(l,1)),cMin(Min(k,0),Min(l,0)),cMin(Min(k,1),Min(l,1));
if(r)
cMax(Max(k,0),Max(r,0)),cMax(Max(k,1),Max(r,1)),cMin(Min(k,0),Min(r,0)),cMin(Min(k,1),Min(r,1));
size(k)=size(l)+size(r)+1;
return;
}
inline void flat(reg int k){
if(lson(k))
flat(lson(k));
p[++cnt]=k;
if(rson(k))
flat(rson(k));
return;
}
int buf[MAXN];
inline int Build(reg int l,reg int r,reg int wd){
if(l>r)
return 0;
WD=wd;
std::nth_element(p+l,p+mid,p+r+1,cmp);
reg int k=p[mid];
Max(k,0)=Min(k,0)=val(k,0),Max(k,1)=Min(k,1)=val(k,1);
lson(k)=Build(l,mid-1,wd^1),rson(k)=Build(mid+1,r,wd^1);
pushup(k);
return k;
}
inline void Insert(reg int& root,reg int c){
if(!root){
root=c;
return;
}
reg int top=0;
for(reg int wd=0,x=root;;wd^=1){
buf[++top]=x;
cMax(Max(x,0),Max(c,0)),cMax(Max(x,1),Max(c,1)),cMin(Min(x,0),Min(c,0)),cMin(Min(x,1),Min(c,1));
++size(x);
if(val(c,wd)<val(x,wd))
if(!lson(x)){
lson(x)=c;
break;
}
else
x=lson(x);
else
if(!rson(x)){
rson(x)=c;
break;
}
else
x=rson(x);
}
buf[++top]=c;
while(size(lson(c))<alpha*size(c)&&size(rson(c))<alpha*size(c))
c=buf[--top];
if(!c)
return;
if(c==root){
cnt=0;
flat(root);
root=Build(1,cnt,0);
cnt=0;
return;
}
reg int fa=buf[--top],crt;
flat(c);
crt=Build(1,cnt,top&1);
cnt=0;
if(lson(fa)==c)
lson(fa)=crt;
else
rson(fa)=crt;
}
inline void Query(reg int x){
if(!x||Max(x,0)<_Min[0]||Max(x,1)<_Min[1]||Min(x,0)>_Max[0]||Min(x,1)>_Max[1]||lastans>=K)
return;
if(_Min[0]<=Min(x,0)&&Max(x,0)<=_Max[0]&&_Min[1]<=Min(x,1)&&Max(x,1)<=_Max[1]){
lastans+=size(x);
return;
}
if(_Min[0]<=val(x,0)&&val(x,0)<=_Max[0]&&_Min[1]<=val(x,1)&&val(x,1)<=_Max[1])
++lastans;
Query(lson(x));
Query(rson(x));
return;
}
#undef lson
#undef rson
}
using kD_Tree::T;
int ct,tot=1;
int root[MAXSIZE],lson[MAXSIZE],rson[MAXSIZE];
inline void Update(void){
reg bool flag=true;
reg int ID=1;
reg int l=1,r=INF;
while(true){
if(flag){
++ct;
Max(ct,0)=Min(ct,0)=val(ct,0)=X[0],Max(ct,1)=Min(ct,1)=val(ct,1)=X[1];
size(ct)=1;
kD_Tree::Insert(root[ID],ct);
}
if(l==r)
return;
if(K<=mid){
if(!lson[ID])
lson[ID]=++tot;
ID=lson[ID],r=mid;
flag=false;
}
else{
if(!rson[ID])
rson[ID]=++tot;
ID=rson[ID],l=mid+1;
flag=true;
}
}
return;
}
inline void Query(void){
lastans=0;
kD_Tree::Query(root[1]);
if(lastans<K){
puts("NAIVE!ORZzyz.");
lastans=0;
return;
}
reg int ID=1,l=1,r=INF;
while(l<r){
lastans=0;
kD_Tree::Query(root[rson[ID]]);
if(K<=lastans)
ID=rson[ID],l=mid+1;
else
K-=lastans,ID=lson[ID],r=mid;
}
printf("%d\n",lastans=l);
return;
}
}
using SegmentTree::lastans;
int main(void){
reg int cnt=0;
read(),n=read();
reg int type,x1,y1,x2,y2;
for(reg int i=1;i<=n;++i)
switch(type=read()){
case 1:{
x1=read()^lastans,y1=read()^lastans,K=read()^lastans;
X[0]=x1,X[1]=y1;
SegmentTree::Update();
++cnt;
break;
}
case 2:{
x1=read()^lastans,y1=read()^lastans,x2=read()^lastans,y2=read()^lastans,K=read()^lastans;
_Min[0]=x1,_Min[1]=y1,_Max[0]=x2,_Max[1]=y2;
SegmentTree::Query();
break;
}
default:break;
}
return 0;
}
近期评论