视频链接：C108 整体二分+树状数组（区修+区查）P3332 [ZJOI2013] K大数查询_哔哩哔哩_bilibili
参考：C82 树状数组 区修+区查 P3372 线段树1 - 董晓 - 博客园 (cnblogs.com)
// 整体二分+树状数组（区修+区查）O(n*logn*logn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=50005;
int n,m,cnt,ans[N];
struct Q{
//查询: opt=2，[x,y]第k大，id编号
//插入: opt=1，[x,y]加入k
int opt,x,y,id; LL k;
}q[N],q1[N],q2[N];
struct BIT{ //树状数组
LL s[N];
void add(int x,int v){ //点修
for(int i=x;i<=n;i+=i&-i)s[i]+=v;
}
LL sum(int x){ //前缀和
LL t=0;
for(int i=x;i;i-=i&-i)t+=s[i];
return t;
}
}a,b; //a:di的区间和, b:di*(i-1)的区间和
void solve(int l,int r,int L,int R){
if(l>r)return;
if(L==R){
for(int i=l;i<=r;i++)ans[q[i].id]=L; return;
}
int mid=(L+R)>>1; //二分值域
int p1=0,p2=0; //分流操作
for(int i=l;i<=r;i++){ //枚举操作
int x=q[i].x,y=q[i].y;
if(q[i].opt==1){ //插入
if(q[i].k>mid) //若k值大，则维护贡献
a.add(x,1),a.add(y+1,-1),
b.add(x,x-1),b.add(y+1,-y),
q2[++p2]=q[i]; //分流到右边
else q1[++p1]=q[i];
}
else{ //查询
LL s=a.sum(y)*y-b.sum(y)
-(a.sum(x-1)*(x-1)-b.sum(x-1));
if(s>=q[i].k) //若s太多，则第k大在右边
q2[++p2]=q[i]; //分流到右边
else q[i].k-=s,q1[++p1]=q[i];
}
}
for(int i=1;i<=p2;i++) //清空贡献
if(q2[i].opt==1){
int x=q2[i].x,y=q2[i].y;
a.add(x,-1),a.add(y+1,1),
b.add(x,-x+1),b.add(y+1,y);
}
for(int i=1;i<=p1;i++) q[l+i-1]=q1[i];
for(int i=1;i<=p2;i++) q[l+p1+i-1]=q2[i];
solve(l,l+p1-1,L,mid);
solve(l+p1,r,mid+1,R); //分治
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){ //操作信息
scanf("%d%d%d%lld",&q[i].opt,&q[i].x,&q[i].y,&q[i].k);
if(q[i].opt==2) q[i].id=++cnt;
}
solve(1,m,-n,n); //整体二分
for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
}
// 整体二分+线段树 O(n*logn*logn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define lc u<<1
#define rc u<<1|1
const int N=50005;
int n,m,cnt,ans[N];
struct Q{
//查询: opt=2，[x,y]第k大，id编号
//插入: opt=1，[x,y]加入k
int opt,x,y,id; LL k;
}q[N],q1[N],q2[N];
struct Tree{ //线段树
int l,r;
LL sum,tag; //区间和，懒标记
}tr[N<<2];
void pushup(int u){ //上传信息
tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int u){ //下传信息
if(!tr[u].tag) return;
int l=tr[u].l,r=tr[u].r,mid=(l+r)>>1;
tr[lc].tag+=tr[u].tag;
tr[rc].tag+=tr[u].tag;
tr[lc].sum+=tr[u].tag*(mid-l+1);
tr[rc].sum+=tr[u].tag*(r-mid);
tr[u].tag=0;
}
void build(int u,int l,int r){ //建树
tr[u]={l,r,0,0};
if(l==r) return;
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void change(int u,int x,int y,LL v){ //区修
int l=tr[u].l,r=tr[u].r;
if(x<=l&&r<=y){
tr[u].tag+=v;
tr[u].sum+=v*(r-l+1);
return;
}
pushdown(u);
int mid=(l+r)>>1;
if(x<=mid) change(lc,x,y,v);
if(mid<y) change(rc,x,y,v);
pushup(u);
}
LL query(int u,int x,int y){ //区查
int l=tr[u].l,r=tr[u].r;
if(x<=l&&r<=y) return tr[u].sum;
pushdown(u);
int mid=(l+r)>>1;LL s=0;
if(x<=mid) s+=query(lc,x,y);
if(mid<y) s+=query(rc,x,y);
return s;
}
void solve(int l,int r,int L,int R){
if(l>r) return;
if(L==R){
for(int i=l;i<=r;i++)ans[q[i].id]=L;
return;
}
int mid=(L+R)>>1; //二分值域
int p1=0,p2=0; //分流操作
for(int i=l;i<=r;i++){ //枚举操作
if(q[i].opt==1){ //插入
if(q[i].k>mid) //若k值大，则维护贡献
change(1,q[i].x,q[i].y,1),
q2[++p2]=q[i]; //分流到右边
else q1[++p1]=q[i];
}
else{ //查询
LL s=query(1,q[i].x,q[i].y);
if(s>=q[i].k) //若s太多，则第k大在右边
q2[++p2]=q[i]; //分流到右边
else q[i].k-=s,q1[++p1]=q[i];
}
}
for(int i=1;i<=p2;i++) //清空贡献
if(q2[i].opt==1)change(1,q2[i].x,q2[i].y,-1);
for(int i=1;i<=p1;i++) q[l+i-1]=q1[i];
for(int i=1;i<=p2;i++) q[l+p1+i-1]=q2[i];
solve(l,l+p1-1,L,mid);
solve(l+p1,r,mid+1,R); //分治
}
int main(){
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=m;i++){ //操作信息
scanf("%d%d%d%lld",&q[i].opt,&q[i].x,&q[i].y,&q[i].k);
if(q[i].opt==2) q[i].id=++cnt;
}
solve(1,m,-n,n); //整体二分
for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
}
标签：P3332,区修,int,区查,LL,tr,++,tag,include From： https://www.cnblogs.com/dx123/p/18100565