lg3332

发表于 | 分类于 ， ， | 阅读数 次

链接:lg3332

题解

  • 线段树套线段树,动态开点,标记下传不方便,而且会T(我会说我T了一次吗…),更快的方法是CDQ分治或者整体二分…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=5e4+7;
const int M=N*400;
ll tr[M],lz[M],C[N],n,m,cnt,rk[N];
int ls[M],rs[M],root[N<<2],A[N],B[N],op[N],len,ct;
template <typename T>inline void read(T &x){
	x=0;char c;int sign=1;
	do{c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9');
	do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
	x*=sign;
}
inline void update(int &o,int l,int r,int L,int R){
    if(!o)o=++cnt;
    tr[o]+=min(r,R)-max(l,L)+1;
    if(L<=l&&R>=r){lz[o]++;return ;}
    int mid=l+r>>1;
    if(L<=mid)update(ls[o],l,mid,L,R);
    if(R>mid)update(rs[o],mid+1,r,L,R);
}
inline void UPDATE(int a,int b,int c){
    int l=1,r=len,k=1;
    while(l<r){
        int mid=l+r>>1;
        update(root[k],1,n,a,b);
        if(c<=mid)k<<=1,r=mid;
        else k=k<<1|1,l=mid+1;
    }
    update(root[k],1,n,a,b);
}
inline ll query(int o,int l,int r,int L,int R){
    if(!o)return 0;
    if(L<=l&&R>=r)return tr[o];
    int mid=l+r>>1;ll ans=lz[o]*(min(r,R)-max(L,l)+1);
    if(L<=mid)ans+=query(ls[o],l,mid,L,R);
    if(R>mid)ans+=query(rs[o],mid+1,r,L,R);
    return ans;
}
inline int QUERY(int a,int b,int c){
    int l=1,r=len,k=1;
    while(l<r){
        int mid=l+r>>1;ll t=query(root[k<<1],1,n,a,b);
        if(c<=t)r=mid,k<<=1;
        else l=mid+1,k=k<<1|1,c-=t;
    }
    return l;
}
int main(){
    read(n);read(m);
	rep(i,1,m){read(op[i]);read(A[i]);read(B[i]);read(C[i]);if(op[i]==1)rk[++ct]=C[i];}
    sort(rk+1,rk+ct+1);
    len=unique(rk+1,rk+ct+1)-rk-1;
    rep(i,1,m)if(op[i]==1)C[i]=lower_bound(rk+1,rk+len+1,C[i])-rk;
    rep(i,1,m){
        if(op[i]==1){UPDATE(A[i],B[i],len-C[i]+1);}
        else printf("%d\n",rk[len-QUERY(A[i],B[i],C[i])+1]);
    }
    return 0;
}