K大数查询
题解
整体二分板子题。
其实看到题目应该很容易想到整体二分的。
我们可以先二分答案，对于权值区间
[
l
,
r
]
[l,r]
[l,r]，我们的询问区间为
[
L
,
R
]
[L,R]
[L,R]。
我们可以用一个树状数组维护前缀和，维护大于
m
i
d
mid
mid的数的数量的前缀和。
我们先将
[
L
,
R
]
[L,R]
[L,R]中大于
m
i
d
mid
mid的操作加到树状数组上，再看询问中有多少应该在左区间
[
l
,
m
i
d
]
[l,mid]
[l,mid]，有多少应该在右区间
(
m
i
d
,
r
]
(mid,r]
(mid,r]。
将在左区间的询问减去右区间的操作的贡献，再进行归并排序。
注意，归并排序后下传的操作与询问序列也应该符合最开始输入的时间顺序，相当于我们要维护两个关键字。
由于树状数组维护的时当前二分区间的前缀和，所以我们每次下传都需要清空树状数组。
总时间复杂度
O
(
n
l
o
g
2
n
)
O\left(nlog^2\,n\right)
O(nlog2n)，比湘妹的树套树与整体二分都要快。
源码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 50005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int INF=0x7f7f7f7f;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
int n,m,ans[MAXN];bool d[MAXN];LL tr1[MAXN],tr2[MAXN];
struct ask{int l,r,typ,id;LL w;}s[MAXN],b[MAXN],c[MAXN];
void insert(int x,LL w){int y=x;while(x<=n)tr1[x]+=w,tr2[x]+=1ll*y*w,x+=lowbit(x);}
LL query(int x){LL res=0,y=x;while(x)res+=1ll*(y+1)*tr1[x]-tr2[x],x-=lowbit(x);return res;}
void sakura(int l,int r,int al,int ar){
if(l>r||al>ar)return ;int mid=l+r>>1,j=0,k=0,id=al;
if(l==r){for(int i=al;i<=ar;i++)ans[s[i].id]=l;return ;}
for(int i=al;i<=ar;i++)
if(s[i].typ&1){if(s[i].w>mid)insert(s[i].l,1),insert(s[i].r+1,-1),c[++k]=s[i];else b[++j]=s[i];}
else{LL now=query(s[i].r)-query(s[i].l-1);if(now>=s[i].w)c[++k]=s[i];else b[++j]=s[i],b[j].w-=now;}
for(int i=al;i<=ar;i++)if((s[i].typ&1)&&s[i].w>mid)insert(s[i].l,-1),insert(s[i].r+1,1);
for(int i=1;i<=j;i++)s[id++]=b[i];for(int i=1;i<=k;i++)s[id++]=c[i];
sakura(l,mid,al,al+j-1);sakura(mid+1,r,al+j,ar);
}
signed main(){
read(n);read(m);
for(int i=1;i<=m;i++)read(s[i].typ),read(s[i].l),read(s[i].r),read(s[i].w),s[i].id=i,d[i]=s[i].typ&1;
sakura(1,n,1,m);for(int i=1;i<=m;i++)if(!d[i])printf("%d\n",ans[i]);
return 0;
}