首先,是一个整体二分的入门题
https://www.luogu.org/problem/P3834
题目很简单,要求快速求解静态区间$[l,r]$的第$K$大元素值
好,先思考一个简单问题
给一个序列,求一次这个序列的第$k$大
有一种二分思路是,我们用计数排序,然后维护它的前缀和
每次直接二分第$k$大的答案$mid$,如果$[1-mid]$的计数前缀和$<=k$,则说明$mid>=$真实答案,否则小于
这个等价于,每次二分,我们都跑一遍全部序列,只有小于$mid$的元素是有效的,,然后拿有效的元素个数和$k$做比较
那么继续看:
对于本题,首先把操作全部放在一起,按照时间顺序就行
注意,对于初始数列的赋值,我们也可以视为一种操作,按顺序放在所有询问的前面就行了
简单来说,保存下这些信息:
{操作类型$tp$,操作区间下限$l$,操作区间上限$r$,操作值$x$/查询值$k$,操作的编号$id$}
而对于赋值操作来说,显然其区间下限和上限都为该点的下标
然后整体二分开始:
我们一口气二分所有的询问,
现在我们记当前询问所回答的操作段为$[s,t]$,二分答案$mid$
即,我们处理$(s,t,l,r)$这个子问题
原来的操作序列记为$q$,再开两个辅助的操作序列$ql,qr$;
如果是赋值操作:
1.$x$小于我们二分的答案$mid$,那么,我们肯定会受到影响,所以在$bit$上在它所赋值的位置上$+1$,
再把这个操作放入$ql$中,因为它可能对更小的$mid$有影响
这里我们类比到一开始的简单问题,就可以理解了,
$bit$实际上维护了整个序列上的有效点,让我们可以快速查找任意区间内的有效点个数
2.$x$大于$mid$,那么我们就不需要管,因为我们暂时不会受到影响,整个点是无效的,我们直接放入qr中,因为它需要对更大mid值的有影响
如果是查询操作:
1.我们类比一开始的简单问题,显然,如果查询的区间$[q[i].l,q[i].r]$内的有效点个数$cnt$小于$k$个,那么我们应该增加$mid$的值,所以放进$qr$中,
但是由于已经拥有$cnt$个满足条件的了,而下一步二分的时候,值域为$mid$以下的操作我们会放入另外一个子问题,
因此,需要把$k$减少$cnt$再放入$qr$
2.如果小于等于$k$个,我们可以尝试减少$mid$的值,所以直接放入$ql$中
处理完$[s,t]$的操作之后,我们将之前做过的赋值全部撤销
最后,显然地,对于$[s,t]$的所有操作,我们分为了2组,$q$l和$qr$,现在我们把$ql$放在前面,$qr$放在后面,
这样我们就对$[s,t]$的操作进行了一次分组,左边$ql$个操作是对答案$[l,mid]$的进行回答/影响的,右边$qr$个操作是对答案$[mid+1,r]$的进行操作/影响的
接着继续二分$(s,s+ql-1,l,mid)$和$(s+ql,mid+1,r)$两个子问题就行了
最后递归到$l==r$的时候,显然此时$[s,t]$的答案就都找到了
复杂度可以认为是$(n+m)log(n+m)log(ValueDomain)$的,
在该问题下,尽管常数很小,但是由于比主席树多了一个log,所以还是慢了2-3倍
但它的优越之处在于,对于静态和动态区间第$k$大,其复杂度都是一样的,
在我们用它解决动态区间第$K$大,三维偏序之类的问题时,就能体现出优越性了
本题代码如下:
#include<bits/stdc++.h>
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;//head
const int maxn=4e5+10,maxm=2e6+10;
int casn,n,m,k,cnt;
class bit{public:
int node[maxn];
inline int lb(int x) {return x&(-x);}
inline void update(int pos,int val){
for(;pos<=n;pos+=lb(pos)) node[pos]+=val;
}
inline int ask(int pos){
int sum=0;
for(;pos>0;pos-=lb(pos)) sum+=node[pos];
return sum;
}
inline int query(int l,int r){
return ask(r)-ask(l-1);
}
}tree;
struct node{int x,l,r,k;}q[maxn],ql[maxn],qr[maxn];
int ans[maxn],b[maxn];
namespace divide{
void dc(int s,int t,int l,int r){
if(l>r||s>t) return ;
if(l==r){
rep(i,s,t) if(q[i].x)ans[q[i].x]=l;
return ;
}
int mid=(l+r)>>1,cntl=0,cntr=0,tmp;
rep(i,s,t){
if(!q[i].x){
if(q[i].k<=mid) ql[++cntl]=q[i],tree.update(q[i].l,1);
else qr[++cntr]=q[i];
}else{
tmp=tree.query(q[i].l,q[i].r);
if(tmp<q[i].k)q[i].k-=tmp,qr[++cntr]=q[i];
else ql[++cntl]=q[i];
}
}
rep(i,1,cntl){
q[s-1+i]=ql[i];
if(!ql[i].x) tree.update(ql[i].l,-1);
}
rep(i,1,cntr)q[s-1+cntl+i]=qr[i];
dc(s,s+cntl-1,l,mid);dc(s+cntl,t,mid+1,r);
}
}
int main() {IO;
cin>>n>>m;
rep(i,1,n) cin>>b[i];
rep(i,1,n) q[i]=(node){0,i,i,b[i]};
int l,r,k;
rep(i,1,m){
cin>>l>>r>>k;
q[n+i]=(node){i,l,r,k};
}
divide::dc(1,n+m,-1e9-10,1e9+10);
rep(i,1,m) cout<<ans[i]<<endl;
}