```cpp
#include<algorithm>
#include<cstdio>
#include<cmath>
const int M=5e4+5;
typedef long long ll;
struct Node{
Node*L,*R;ll val;
}t[M*100],*tot=t;
int n,m,len,s[M];
Node*root1[M],*root2[M];
Node**cnt[4],*tmp[4][M];
int mdf[4]={0,-1,0,-1};
struct query{
int opt,L,R;ll val;
}q[M];
void change(Node*&u,int L,int R,int x,ll val){
if(u==NULL)u=++tot;
u->val+=val;
if(L<R){
int mid=L+R>>1;
if(x<=mid)change(u->L,L,mid,x,val);
else change(u->R,mid+1,R,x,val);
}
}
inline void add(Node**s,int x,int a,ll val){
for(int i=x;i<=n;i+=1<<__builtin_ctz(i)){
change(s[i],1,len,a,val);
}
}
inline void modify(int L,int R,int x,ll val=1){
add(root1,L,x,val);
add(root1,R+1,x,-val);
add(root2,L,x,(L-1)*val);
add(root2,R+1,x,R*-val);
}
int get_kth(int L,int R,ll k){
if(L==R)return L;
int j,mid=L+R>>1;ll sum=0;
for(j=0;j<4;++j){
for(Node**i=tmp[j];i!=cnt[j];++i){
sum+=mdf[j]*(*i)->L->val;
}
}
if(sum<=k){
for(j=0;j<4;++j){
for(Node**i=tmp[j];i!=cnt[j];++i){
*i=(*i)->L;
}
}
return get_kth(L,mid,k);
}
else{
for(j=0;j<4;++j){
for(Node**i=tmp[j];i!=cnt[j];++i){
*i=(*i)->R;
}
}
return get_kth(mid+1,R,k);
}
}
inline int kth(int L,int R,ll k){
int i;
for(i=0;i<4;++i)cnt[i]=tmp[i];
for(i=L-1;i;i-=1<<__builtin_ctz(i))*cnt[0]++=root1[i];
for(i=L-1;i;i-=1<<__builtin_ctz(i))*cnt[1]++=root2[i];
for(i=R;i;i-=1<<__builtin_ctz(i))*cnt[2]++=root1[i];
for(i=R;i;i-=1<<__builtin_ctz(i))*cnt[3]++=root2[i];
mdf[0]=L-1;mdf[2]=R;
return get_kth(1,len,k);
}
signed main(){
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i){
scanf("%d%d%d%lld",&q[i].opt,&q[i].L,&q[i].R,&q[i].val);
if(q[i].opt==1)s[++len]=q[i].val;
}
std::sort(s+1,s+len+1);
len=std::unique(s+1,s+len+1)-s-1;
for(i=1;i<=m;++i){
if(q[i].opt==1){
q[i].val=std::lower_bound(s+1,s+len+1,q[i].val)-s;
modify(q[i].L,q[i].R,q[i].val);
}
if(q[i].opt==2){
printf("%d\n",s[kth(q[i].L,q[i].R,q[i].val)]);
}
}
}
```
by Prean @ 2020-07-04 02:09:20
~~qndmx~~
by disangan233 @ 2020-07-04 08:08:36
草
回头一看，getkth写错了
走右边k应该剪去sum
by Prean @ 2020-07-08 18:29:36
qndmx
by Stinger @ 2020-12-17 11:33:56