bzoj3110 [Zjoi2013]K大數查詢

​​http://www.elijahqi.win/2018/03/01/bzoj3110/​​​

Description

有N個位置，M個操作。操作有兩種，每次操作如果是1 a b c的形式表示在第a個位置到第b個位置，每個位置加入一個數c

如果是2 a b c形式，表示詢問從第a個位置到第b個位置，第C大的數是多少。

Input

第一行N，M

接下來M行，每行形如1 a b c或2 a b c

Output

輸出每個詢問的結果

Sample Input

2 5

1 1 2 1

1 1 2 2

2 1 1 2

2 1 1 1

2 1 2 3

Sample Output

1

2

1

HINT

【樣例說明】

第一個操作 後位置 1 的數隻有 1 ， 位置 2 的數也隻有 1 。 第二個操作 後位置 1

的數有 1 、 2 ，位置 2 的數也有 1 、 2 。 第三次詢問 位置 1 到位置 1 第 2 大的數 是

1 。 第四次詢問 位置 1 到位置 1 第 1 大的數是 2 。 第五次詢問 位置 1 到位置 2 第 3

大的數是 1 。‍

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=Maxlongint

#include<cstdio>
#include<algorithm>
#define N 55000
#define ll long long
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(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x*f;
}
struct node{
    int op,a,b,c;
}qr[N];
int n,m,num,cnt,a1[N],nn,rt[N*20],root;
struct node1{
    int left,right;ll s;int lazy;
}tree[N<<1],tr[N*400];
inline void build(int &x,int l,int r){
    x=++num;if (l==r) return;int mid=l+r>>1;
    build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);
}
inline void pushdown(int x,int l,int r){
    if (!tr[x].lazy) return;int mid=l+r>>1;
    if (!tr[x].left) tr[x].left=++cnt;
    if (!tr[x].right) tr[x].right=++cnt;
    int lc=tr[x].left,rc=tr[x].right;
    tr[lc].lazy+=tr[x].lazy;tr[rc].lazy+=tr[x].lazy;
    tr[lc].s+=(ll)tr[x].lazy*(mid-l+1);
    tr[rc].s+=(ll)tr[x].lazy*(r-mid);
    tr[x].lazy=0;
}
inline void ins(int &x,int l,int r,int l1,int r1){
    if (!x) x=++cnt;if(l1<=l&&r1>=r) {++tr[x].lazy;tr[x].s+=r-l+1;return;}
    int mid=l+r>>1;pushdown(x,l,r);if (l1<=mid) ins(tr[x].left,l,mid,l1,r1);
    if (r1>mid) ins(tr[x].right,mid+1,r,l1,r1);
    tr[x].s=tr[tr[x].left].s+tr[tr[x].right].s;
}
inline void insert1(int x,int l,int r,int p,int l1,int r1){
    ins(rt[x],1,n,l1,r1);if (l==r) return;int mid=l+r>>1;
    if (p<=mid) insert1(tree[x].left,l,mid,p,l1,r1);else insert1(tree[x].right,mid+1,r,p,l1,r1);
}
inline ll query(int &x,int l,int r,int l1,int r1){
    if (!x) return 0;int mid=l+r>>1;ll tmp=0;
    if (l1<=l&&r1>=r) return tr[x].s;pushdown(x,l,r);
    if (l1<=mid) tmp+=query(tr[x].left,l,mid,l1,r1);
    if (r1>mid) tmp+=query(tr[x].right,mid+1,r,l1,r1);return tmp;
}
inline int qk(int x,int l,int r,int k,int l1,int r1){
    if (l==r) return l;int mid=l+r>>1;ll tmp=query(rt[tree[x].right],1,n,l1,r1);
    if (k<=tmp) return qk(tree[x].right,mid+1,r,k,l1,r1);
    return qk(tree[x].left,l,mid,k-tmp,l1,r1);
}
int main(){
    freopen("bzoj3110.in","r",stdin);
    n=read();m=read();
    for (int i=1;i<=m;++i){
        qr[i].op=read();qr[i].a=read();qr[i].b=read();qr[i].c=read();
        if (qr[i].op==1) a1[++nn]=qr[i].c;
    }sort(a1+1,a1+nn+1);nn=unique(a1+1,a1+nn+1)-a1-1;build(root,1,nn);
    for (int i=1;i<=m;++i){
        if (qr[i].op==1){
            qr[i].c=lower_bound(a1+1,a1+nn+1,qr[i].c)-a1;
            insert1(root,1,nn,qr[i].c,qr[i].a,qr[i].b);
        }
        if (qr[i].op==2) printf("%d\n",a1[qk(root,1,nn,qr[i].c,qr[i].a,qr[i].b)]);
    }
    return 0;
}