分析
虽然树套树也可以做，这里考虑整体二分，
对于二分的答案(mid)，1操作实际上就是如果(c>mid)就给区间整体加1，
2操作即询问区间和是否超过(k)，如果超过(k)就在([mid+1,r])中找答案
简单的区间加可以用树状数组实现
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=200011; typedef long long lll;
struct rec{int l,r; lll x; int rk;}q[N],q1[N],q2[N];
lll ans[N],b[N],n,m,tot,T;
inline lll iut(){
rr lll ans=0,f=1; rr char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans*f;
}
inline void print(lll ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
struct Tree_Array{
lll c[N];
inline void update(int x,lll y){
for (;x<=n;x+=-x&x) c[x]+=y;
}
inline lll query(int x){
rr lll ans=0;
for (;x;x-=-x&x) ans+=c[x];
return ans;
}
}c0,c1;
inline void dfs(int L,int R,int l,int r){
if (l>r) return;
if (L==R){
for (rr int i=l;i<=r;++i)
if (q[i].rk) ans[q[i].rk]=b[L];
return;
}
rr int mid=(L+R)>>1,tot1=0,tot2=0;
for (rr int i=l;i<=r;++i)
if (q[i].rk){
rr lll now=c0.query(q[i].r)*q[i].r-c1.query(q[i].r)-c0.query(q[i].l-1)*(q[i].l-1)+c1.query(q[i].l-1);
if (q[i].x<=now) q2[++tot2]=q[i];
else q[i].x-=now,q1[++tot1]=q[i];
}else if (q[i].x>mid)
c0.update(q[i].l,1),c1.update(q[i].l,q[i].l-1),c0.update(q[i].r+1,-1),c1.update(q[i].r+1,-q[i].r),q2[++tot2]=q[i];
else q1[++tot1]=q[i];
for (rr int i=l;i<=r;++i)
if (!q[i].rk&&q[i].x>mid)
c0.update(q[i].l,-1),c1.update(q[i].l,1-q[i].l),c0.update(q[i].r+1,1),c1.update(q[i].r+1,q[i].r);
for (rr int i=1;i<=tot1;++i) q[l+i-1]=q1[i];
for (rr int i=1;i<=tot2;++i) q[l+i+tot1-1]=q2[i];
dfs(L,mid,l,l+tot1-1),dfs(mid+1,R,l+tot1,r);
}
signed main(){
n=iut(),m=iut();
for (rr int i=1;i<=m;++i){
rr int opt=iut(),l=iut(),r=iut(); rr lll x=iut();
q[i]=(rec){l,r,x,0};
if (opt==1) b[++tot]=x;
else q[i].rk=++T;
}
sort(b+1,b+1+tot),tot=unique(b+1,b+1+tot)-b-1;
for (rr int i=1;i<=m;++i) if (!q[i].rk)
q[i].x=lower_bound(b+1,b+1+tot,q[i].x)-b;
dfs(1,tot,1,m);
for (rr int i=1;i<=T;++i) print(ans[i]),putchar(10);
return 0;
}