bzoj 4604 The kth maximum number

​​http://www.elijahqi.win/archives/3720​​​

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

#include<cstdio>
#include<cctype>
#include<algorithm>
using 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]<tree[b].x[D];
}
inline void build(int &x,int l,int r,int d){
    int mid=l+r>>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 (l<mid) build(tree[x].left,l,mid-1,d^1);
    if (r>mid) 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].x[d]) {
        if ((tree[l].size+1)*4>(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]<x1||tree[x].mx[1]<y1||tree[x].mn[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])<k) {puts("NAIVE!ORZzyz.");continue;}
            printf("%d\n",qr(root,1,1000000000,k));
        }
    }
    return 0;
}