树套树，权值线段树套序列线段树，每次在在权值线段树上的每棵子树上做区间加，查询的时候左右子树二分
本来想两个都动态开点的，这样能体现树套树在线的优越性。但是常数太大惹，所以外层直接固定建树了QAQ
就是不写整体二分╭(╯^╰)╮
Warning：Extremely ugly code detected
// luogu-judger-enable-o2
//I CAN PASS THE TEST
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m,f,op,tot;
long long val[N];
int root[N],lson[N],rson[N],laz[N];
void read1(int &x)
{
x=; char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
}
void read2(int &x)
{
x=f=; char ch=getchar();
while(!isdigit(ch))
f|=ch=='-',ch=getchar();
while(isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
x=f?-x:x;
}
void read3(long long &x)
{
x=; char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
}
void write(int x)
{
if(x>) write(x/);
putchar(x%|);
}
void Insert(int &nde,int ll,int rr,int l,int r)
{
if(ll>r||rr<l) return ;
if(!nde) nde=++tot;
val[nde]+=min(r,rr)-max(l,ll)+;
if(ll>=l&&rr<=r)
++laz[nde];
else
{
int mid=(ll+rr)>>;
Insert(lson[nde],ll,mid,l,r);
Insert(rson[nde],mid+,rr,l,r);
}
}
void Add(int l,int r,int v)
{
int nde=,ll=,rr=*n;
while(true)
{
Insert(root[nde],,n,l,r);
if(ll^rr)
{
int mid=(ll+rr)>>;
(v<=mid)?(nde<<=,rr=mid):(nde<<=,nde|=,ll=mid+);
}
else return ;
}
}
long long Query(int nde,int ll,int rr,int l,int r,int lz)
{
if(ll>r||rr<l)
return ;
else if(ll>=l&&rr<=r)
return val[nde]+1ll*lz*(rr-ll+);
else
{
int mid=(ll+rr)>>;
return Query(lson[nde],ll,mid,l,r,lz+laz[nde])+Query(rson[nde],mid+,rr,l,r,lz+laz[nde]);
}
}
int main()
{
register int i;
read1(n),read1(m);
for(i=;i<=m;i++)
{
read1(op);
if(op==)
{
int t1,t2,t3;
read1(t1),read1(t2),read2(t3);
int nde=,ll=,rr=*n; t3=n-t3+;
while(true)
{
Insert(root[nde],,n,t1,t2);
if(!(ll^rr)) break;
int mid=(ll+rr)>>;
(t3<=mid)?(nde<<=,rr=mid):(nde<<=,nde|=,ll=mid+);
}
}
else
{
int t1,t2; long long t4;
read1(t1),read1(t2),read3(t4);
int nde=,ll=,rr=*n;
while(true)
{
if(ll==rr) {write(n-ll+),puts(""); break;}
int mid=(ll+rr)/;
long long qry=Query(root[nde<<],,n,t1,t2,);
(t4<=qry)?(nde<<=,rr=mid):(nde<<=,nde|=,ll=mid+,t4-=qry);
}
}
}
return ;
}