首页 > 代码库 > 【BZOJ4605】崂山白花蛇草水 权值线段树+kd-tree
【BZOJ4605】崂山白花蛇草水 权值线段树+kd-tree
【BZOJ4605】崂山白花蛇草水
Description
神犇Aleph在SDOI Round2前立了一个flag:如果进了省队,就现场直播喝崂山白花蛇草水。凭借着神犇Aleph的实力,他轻松地进了山东省省队,现在便是他履行诺言的时候了。蒟蒻Bob特地为他准备了999,999,999,999,999,999瓶崂山白花蛇草水,想要灌神犇Aleph。神犇Aleph求(跪着的)蒟蒻Bob不要灌他,由于神犇Aleph是神犇,蒟蒻Bob最终答应了他的请求,但蒟蒻Bob决定将计就计,也让神犇Aleph回答一些问题。具体说来,蒟蒻Bob会在一个宽敞的广场上放置一些崂山白花蛇草水(可视为二维平面上的一些整点),然后询问神犇Aleph在矩形区域(x1, y1), (x2, y2)(x1≤x2且y1≤y2,包括边界)中,崂山白花蛇草水瓶数第k多的是多少。为了避免麻烦,蒟蒻Bob不会在同一个位置放置两次或两次以上的崂山白花蛇草水,但蒟蒻Bob想为难一下神犇Aleph,希望他能在每次询问时立刻回答出答案。神犇Aleph不屑于做这种问题,所以把这个问题交给了你。
Input
输入的第一行为两个正整数N, Q,表示横纵坐标的范围和蒟蒻Bob的操作次数(包括放置次数和询问次数)。
接下来Q行,每行代表蒟蒻Bob的一个操作,操作格式如下:
首先第一个数字type,表示操作种类。type=1表示放置,type=2表示询问。
若type=1,接下来会有三个正整数x, y, v,表示在坐标整点(x, y)放置v瓶崂山白花蛇草水。(1≤x, y≤N, 1≤v≤10^9)
若type=2,接下来会有五个正整数x1, y1, x2, y2, k,表示询问矩形区域(x1, y1), (x2, y2)中,崂山白花蛇草水瓶数第k多的是多少。
(1≤x1≤x2≤N,1≤y1≤y2≤N,1≤k≤Q)
为了体现程序的在线性,你需要将每次读入的数据(除了type值)都异或lastans,其中lastans表示上次询问的答案。如果上次询问的答案为"NAIVE!ORZzyz."(见样例输出),则将lastans置为0。初始时的lastans为0。
初始时平面上不存在崂山白花蛇草水。
本题共有12组测试数据。对于所有的数据,N≤500,000。
Q的范围见下表:
测试点1-2 Q=1,000
测试点3-7 Q=50,000
测试点8-12 Q=100,000
Output
对于每个询问(type=2的操作),回答崂山白花蛇草水瓶数第k多的是多少。若不存在第k多的瓶数,请输出"NAIVE!ORZzyz."(输出不含双引号)。
Sample Input
10 7
1 1 1 1
1 2 2 3
1 4 1 2
1 3 4 4
2 1 1 4 1 3
2 2 2 3 5 4
2 2 1 4 4 2
1 1 1 1
1 2 2 3
1 4 1 2
1 3 4 4
2 1 1 4 1 3
2 2 2 3 5 4
2 2 1 4 4 2
Sample Output
NAIVE!ORZzyz.
NAIVE!ORZzyz.
3
NAIVE!ORZzyz.
3
题解:本题的做法好像挺多,kd-tree套平衡树(TLE),替罪羊套kd-tree(两次重构吓人,但是快的飞起)。然而我选择的是较易实现的权值线段树+kd-tree。
用权值线段树维护排名,然后对于每个节点都开一个kd-tree,统计既在当前排名,又在区间中的数有多少。然而数据比较坑,逼着你写重构,所以需要在每个节点对应的kd-tree失去平衡性后单独对当前的kd-tree重构。这里我用了链表记录每个点的kd-tree中的所有节点的编号,具体实现不详细解释。
然而自从加了重构,构造的数据可以过了,但是随机大数据卡的飞起,于是采用了某种猥琐的手段,求不hack~
对了,在此声明一下,有时我做完题后不知道就把源代码扔哪了,写题解的时候随手粘个东西就发上来了,所以下面放的代码有可能无法AC,如果发现这种情况欢迎指出,谢谢~
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N=1000000000;const int maxn=2500010;int n,m,L[2],R[2],D,cntl,scnt,tcnt,ecnt,ans,sroot;struct kd{ int v[2],sm[2],sn[2],siz,ls,rs; kd (){} kd (int a,int b){v[0]=sm[0]=sn[0]=a,v[1]=sm[1]=sn[1]=b,siz=1,ls=rs=0;}};kd t[maxn],p[100010];int to[maxn],next[maxn],pos[100010];struct sag{ int rt,siz,head,ls,rs; void add(int x) { to[++ecnt]=x,next[ecnt]=head,head=ecnt;}}s[maxn];int rd(){ int ret=0; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) gc=getchar(); while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret;}bool cmp(kd a,kd b){ return (a.v[D]==b.v[D])?(a.v[D^1]<b.v[D^1]):(a.v[D]<b.v[D]);}void pushup(int x,int y){ kd *tx=t+x,*ty=t+y; tx->sm[0]=max(tx->sm[0],ty->sm[0]),tx->sn[0]=min(tx->sn[0],ty->sn[0]); tx->sm[1]=max(tx->sm[1],ty->sm[1]),tx->sn[1]=min(tx->sn[1],ty->sn[1]); tx->siz+=ty->siz;}int build(int l,int r,int d){ if(l>r) return 0; D=d; int mid=l+r>>1,x=pos[mid]; nth_element(p+l,p+mid,p+r+1,cmp); kd *tx=t+x; t[x]=p[mid],tx->ls=build(l,mid-1,d),tx->rs=build(mid+1,r,d^1); if(tx->ls) pushup(x,tx->ls); if(tx->rs) pushup(x,tx->rs); return x;}void insert(int x,int y){ D=0; while(x!=y) { pushup(x,y); if(cmp(t[x],t[y])) { if(!t[x].rs) t[x].rs=y; x=t[x].rs; } else { if(!t[x].ls) t[x].ls=y; x=t[x].ls; } D^=1; }}void count(int x){ kd *tx=t+x; if(!x||tx->sm[0]<L[0]||tx->sn[0]>R[0]||tx->sm[1]<L[1]||tx->sn[1]>R[1]) return ; if(tx->sn[0]>=L[0]&&tx->sm[0]<=R[0]&&tx->sn[1]>=L[1]&&tx->sm[1]<=R[1]) { cntl+=tx->siz; return ; } if(tx->v[0]>=L[0]&&tx->v[0]<=R[0]&&tx->v[1]>=L[1]&&tx->v[1]<=R[1]) cntl++; count(tx->ls),count(tx->rs);}void updata(int l,int r,int &x,int c,int a,int b){ if(!x) x=++scnt; sag *sx=s+x; sx->siz++,t[++tcnt]=kd(a,b),sx->add(tcnt); if(m==50000&&sx->siz==2000) { sx->siz=0,pos[0]=0; for(int i=sx->head;i;i=next[i]) pos[++pos[0]]=to[i],p[pos[0]]=kd(t[to[i]].v[0],t[to[i]].v[1]); sx->rt=build(1,pos[0],0); } else { if(!sx->rt) sx->rt=tcnt; else insert(sx->rt,tcnt); } if(l==r) return ; int mid=l+r>>1; if(c<=mid) updata(l,mid,sx->ls,c,a,b); else updata(mid+1,r,sx->rs,c,a,b);}int query(int l,int r,int x,int a){ if(!x) return 0; if(l==r) return l; sag *sx=s+x; int mid=l+r>>1; cntl=0,count(s[sx->rs].rt); if(cntl>=a) return query(mid+1,r,sx->rs,a); return query(l,mid,sx->ls,a-cntl);}int main(){ n=rd(),m=rd(); int i,a,b,c; for(i=1;i<=m;i++) { if(rd()==1) { a=rd()^ans,b=rd()^ans,c=rd()^ans; updata(1,N,sroot,c,a,b); } else { L[0]=rd()^ans,L[1]=rd()^ans,R[0]=rd()^ans,R[1]=rd()^ans,a=rd()^ans,cntl=0; count(s[1].rt); if(cntl<a) printf("NAIVE!ORZzyz.\n"),ans=0; else ans=query(1,N,sroot,a),printf("%d\n",ans); } } return 0;}
【BZOJ4605】崂山白花蛇草水 权值线段树+kd-tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。