bzoj 4604 The kth maximum number

bzoj 4604 The kth maximum number

​​ Description 神犇Aleph在陪蒟蒻Bob玩一个游戏。神犇Aleph随手在地面上画了一个巨大无比的二维平面，然后在其上做一些微 小的贡献或教蒟蒻Bob做人。由于神犇Aleph是队爷，所以有时他会施用”队爷光环”这一魔法，在二维平面上的某坐 标整点处添加一个权值为v的贡献；又由于神犇Aleph是神犇，所以有时他会施用”嘲讽”这一技能，询问蒟蒻Bob在 矩形区域(x1, y1), (x2, y2)(x1≤x2且y1≤y2，包括边界)中，神犇Aleph所做的第k大的贡献是多少。由于神犇Al eph是Au爷，所以他不会在同一个坐标整点处做两次或两次以上的贡献。现在神犇Aleph希望蒟蒻Bob回答他的每次 询问。然而蒟蒻Bob傻傻不会做，于是来求助您，宇宙第一神犇，请您来回答神犇Aleph的每次询问。 Input 输入的第一行为两个正整数N, Q，表示横纵坐标的范围和神犇Aleph的操作次数（包括贡献次数和询问次数）。 接下来Q行，每行代表神犇Aleph的一个操作，操作格式如下： 首先第一个数字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) 初始时平面上不存在贡献。 本题共有7组测试数据。对于所有的数据，N≤500,000。 Q的范围见下表： 测试点1-2 Q=1,000 测试点3-7 Q=50,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 Sample Output NAIVE!ORZzyz. NAIVE!ORZzyz. 3 HINT

Source Idea By Aleph, Description & Data cases By jinlifu1999.

权值线段树套 kd-tree

每一个权值线段树 每个节点维护一个kd-tree 然后查询的时候 在权值线段树上二分 每到一个节点就去kd-tree上查询一下这个区间有多少个点 但是因为每次都在插入 kd-tree无法保证平衡

所以考虑利用替罪羊的思想 每次子树不满足条件就重构

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int inf=0x3f3f3f3f;struct node{ int d[2]; int& operator [](int x){return d[x];}}P;const int N=55000;int root,D,n,Q,x1,y1,x2,y2,q[N],top,num,cnt,rt[N*30];struct node1{ node x;int mn[2],mx[2],left,right,size;}tree[N*30];struct node2{ int left,right;}tr[N*30];inline void update(int x){ int l=tree[x].left,r=tree[x].right; for (int i=0;i<2;++i) tree[x].mn[i]=min(tree[x].x[i],min(tree[l].mn[i],tree[r].mn[i])); for (int i=0;i<2;++i) tree[x].mx[i]=max(tree[x].x[i],max(tree[l].mx[i],tree[r].mx[i])); tree[x].size=tree[l].size+tree[r].size+1;}inline void dfs(int x){ if(!x) return;q[++top]=x; dfs(tree[x].left);dfs(tree[x].right);}inline bool cmp(const int &a,const int &b){ return tree[a].x[D]>1;D=d;nth_element(q+l,q+mid,q+r+1,cmp);x=q[mid]; for (int i=0;i<2;++i) tree[x].mn[i]=tree[x].mx[i]=tree[x].x[i]; tree[x].left=tree[x].right=0;tree[x].size=1; if (lmid) build(tree[x].right,mid+1,r,d^1);update(x);}inline void rebuild(int &x,int d){ top=0;dfs(x);build(x,1,top,d);}inline void insert1(int &x,int d,bool flag){ if (!x) {x=++cnt;tree[x].x=P;update(x);return;} int l=tree[x].left,r=tree[x].right;bool tag=0; if (P[d](tree[x].size+1)*3) insert1(tree[x].left,d^1,1),tag=1; else insert1(tree[x].left,d^1,flag); }else{ if ((tree[r].size+1)*4>(tree[x].size+1)*3) insert1(tree[x].right,d^1,1),tag=1; else insert1(tree[x].right,d^1,flag); }update(x); if (tag&&!flag) rebuild(x,d);}inline int query(int x){ if (!x) return 0; if (x1<=tree[x].mn[0]&&y1<=tree[x].mn[1]&&x2>=tree[x].mx[0]&&y2>=tree[x].mx[1]) return tree[x].size; if (tree[x].mx[0]x2||tree[x].mn[1]>y2) return 0; int tmp=(tree[x].x[0]<=x2&&tree[x].x[0]>=x1&&tree[x].x[1]<=y2&&tree[x].x[1]>=y1); tmp+=query(tree[x].left)+query(tree[x].right);return tmp;}inline void ins(int &x,int l,int r,int p){ if (!x) x=++num;insert1(rt[x],0,0); if (l==r) return;int mid=l+r>>1; if (p<=mid) ins(tr[x].left,l,mid,p); else ins(tr[x].right,mid+1,r,p);}inline int qr(int x,int l,int r,int k){ if (l==r) return l;int mid=l+r>>1; int tmp=query(rt[tr[x].right]); if(k<=tmp) return qr(tr[x].right,mid+1,r,k); else return qr(tr[x].left,l,mid,k-tmp);}int main(){ freopen("bzoj4604.in","r",stdin); n=read();Q=read();tree[0].mn[0]=tree[0].mn[1]=inf; tree[0].mx[0]=tree[0].mx[1]=0; while(Q--){ int op=read(); if (op==1){ int x=read(),y=read(),v=read(); P[0]=x;P[1]=y;ins(root,1,1000000000,v); }else{ x1=read(),y1=read(),x2=read(),y2=read();int k=read(); if (query(rt[1])

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。