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
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
#define ll long long
#define mid ((l+r)>>1)
const int MAXN = 51000;

namespace fast_io{
    //...
}using namespace fast_io;

struct ZKW{
    //区间修改、求和zkw线段树
    ll sumn[MAXN<<2],addn[MAXN<<2];
    int M;
    void init(int n){
        for(M = 1;M<=n+2;M<<=1);
    }
    void update(int l,int r,ll d){
        int i=1,L=0,R=0;
        for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1,i<<=1){
            sumn[l]+=L*d,sumn[r]+=R*d;
            if(~l&1) addn[l^1]+=d,sumn[l^1]+=d*i,L+=i;
            if(r&1) addn[r^1]+=d,sumn[r^1]+=d*i,R+=i;
        }
        sumn[l]+=L*d,sumn[r]+=R*d;
        while(l>>=1) sumn[l]+=(L+R)*d;
    }
    ll query(int l,int r){
        ll ans = 0;int i=1,L=0,R=0;
        for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1,i<<=1){
            ans+=addn[l]*L,ans+=addn[r]*R;
            if(~l&1) ans+=sumn[l^1],L+=i;
            if(r&1) ans+=sumn[r^1],R+=i;
        }
        ans+=addn[l]*L,ans+=addn[r]*R;
        while(l>>=1) ans+=addn[l]*(L+R);
        return ans;
    }
}tree;

struct Q{
    int o,ql,qr;
    ll k;
    // o == 0 -> update l r val; o == 1 -> query l r k
    Q(){}
    Q(int a,int b,int c,ll d):o(a),ql(b),qr(c),k(d){}
}query[MAXN];

int tl[MAXN],tr[MAXN],ans[MAXN];

void solve(int *a,int n,int l,int r){
    //表示要处理的询问在q[0]->q[n-1]，二分答案范围为[l,r]
    if(n == 0) return;//一个微小的剪枝
    if(l == r){
        //递归边界
        for(int i = 0;i<n;i++) ans[a[i]] = l;
        return;
    }
    int n1 = 0,n2 = 0;ll sum;
    for(int i = 0;i<n;i++){
        Q &q = query[a[i]];
        if(q.o == 1){
            //修改如果值大于mid，就应用修改；否则不管
            if(q.k > mid) tree.update(q.ql,q.qr,1),tr[n2++] = a[i];
            else tl[n1++] = a[i];
        }
        else if(q.o == 2){
            //查询的结果sum大于k，二分到右边；否则左边
            sum = tree.query(q.ql,q.qr);
            if(q.k <= sum) tr[n2++] = a[i];
            else q.k -= sum,tl[n1++] = a[i];
        }
    }
    //原样减回去
    for(int i = 0;i<n;i++){
        Q &q = query[a[i]];
        if(q.o == 1 && q.k > mid) tree.update(q.ql,q.qr,-1);
    }
    memcpy(a,tl,sizeof(int) * n1),memcpy(a+n1,tr,sizeof(int) * n2);
    //递归二分
    solve(a,n1,l,mid),solve(a+n1,n2,mid+1,r);
}

int n,m,t[MAXN];

void init(){
    read(n),read(m);
    tree.init(n);
    int op,l,r;ll c;
    for(int i = 0;i<m;i++){
        read(op),read(l),read(r),read(c);
        query[i] = Q(op,l,r,c);
        t[i] = i;
    }
}

void solve(){
    solve(t,m,-n,n);
    for(int i = 0;i<m;i++){
        if(query[i].o == 2)
            print(ans[i]),print('\n');
    }
}

int main(){
    init();
    solve();
    flush();
    return 0;
}