[文章目录]
Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。N,M<=50000,abs(c)<=N
权值线段树套线段树维护区间的个数。
外层维护权值，内层维护外层该权值区间下的所有权值在每个区间的个数。
对于一个修改，我们在外层含有c的区间的内层区间[a,b]+1
对于询问，我们在外层二分，内层查询在该区间的权值个数。
时间复杂度
#include <cstdio>
#include <cstring>
#include <algorithm>
#define U unsigned
using namespace std;
struct seg
{
int ls,rs;
U int lz,siz;
}t[30000000];
int tot;
inline void pushup(int pos)
{
t[pos].siz=t[t[pos].ls].siz+t[t[pos].rs].siz;
}
inline void pushdown(int pos,int l,int r)
{
if(t[pos].lz)
{
int mid=(l+r)>>1,ls,rs;
if(!t[pos].ls) t[pos].ls=++tot;
if(!t[pos].rs) t[pos].rs=++tot;
ls=t[pos].ls; rs=t[pos].rs;
t[ls].siz+=t[pos].lz*(mid-l+1);
t[rs].siz+=t[pos].lz*(r-mid);
t[ls].lz+=t[pos].lz;
t[rs].lz+=t[pos].lz;
t[pos].lz=0;
}
}
void fix(int &pos,int l,int r,int x,int y)
{
if(!pos) pos=++tot;
if(x<=l&&y>=r)
{
t[pos].siz+=r-l+1;
t[pos].lz++; return ;
}
int mid=(l+r)>>1; pushdown(pos,l,r);
if(y<=mid) fix(t[pos].ls,l,mid,x,y);
else if(x>mid) fix(t[pos].rs,mid+1,r,x,y);
else fix(t[pos].ls,l,mid,x,y),fix(t[pos].rs,mid+1,r,x,y);
pushup(pos);
}
U int query(int pos,int l,int r,int x,int y)
{
if(!pos) return 0;
if(x<=l&&y>=r) return t[pos].siz;
int mid=(l+r)>>1; pushdown(pos,l,r);
if(y<=mid) return query(t[pos].ls,l,mid,x,y);
else if(x>mid) return query(t[pos].rs,mid+1,r,x,y);
else return query(t[pos].ls,l,mid,x,y)+query(t[pos].rs,mid+1,r,x,y);
}
int n,m;
int rt[401000];
int main()
{
scanf("%d%d",&n,&m);
U int tmp; int sw,a,b,c,L,R,Mid,P;
while(m--)
{
scanf("%d%d%d%d",&sw,&a,&b,&c);
if(sw&1)
{
c+=n; L=0,R=n<<1,P=1;
while(L<R)
{
fix(rt[P],1,n,a,b);
Mid=(L+R)>>1;
if(c<=Mid) R=Mid,P=P<<1;
else L=Mid+1,P=P<<1|1;
}
fix(rt[P],1,n,a,b);
}
else
{
L=0,R=n<<1,P=1;
while(L<R)
{
Mid=(L+R)>>1;
tmp=query(rt[P<<1|1],1,n,a,b);
if((U int)c<=tmp) P=P<<1|1,L=Mid+1;
else c-=tmp,P=P<<1,R=Mid;
}
printf("%d\n",L-n);
}
}
return 0;
}