整体二分解决静态区间第 k 小的优化

· · 个人记录

首先他是可以做到 O(n\log n) 的。

相比原来的整体二分多了一个对原数组的排序。在把区间放进数组里面的时候就拆成 [1,r]-[1,l-1]（负号可以压在一个 word 里）。这部分也要按 [1,k] 的 k 排序。这样在整体二分求有多少个数在区间 [l,r] 中的时候就可以直接指针扫描过去然后相减了。

原来的整体二分：https://www.luogu.com.cn/record/51628806

现在的整体二分：https://www.luogu.com.cn/record/51627962

可以看到速度有所提升。不过有一个劣势就是拆开区间和离线保存答案的时候增大了空间开销（我们不考虑把空间压在已经使用过的无用数组里的方法，这样不够一般化）。不过一个显然的优点是省去了 bit 数组的开销，还有一个隐式的优点在于不用存 r，即空间开销乘上了一个 0.8 的常数。所以事实上差别并不大。

原本的空间开销为 3n+2m，现在变为了 2n+5m。开销大约是原本的 \dfrac 7 5 \times 0.8=1.12 倍。

所以我们还需要一个对于这种方法的常数优化。事实上这个优化也可以用于普通的整体二分。

我们发现数组和询问混杂起来了以至于还要存一个 opt。。太浪费了，不妨整体二分的时候额外的传一个 (L2,R2) 的参数。即前 n 个数存原数组，后面的存询问。

这样做还有一个好处，就是我们可以进行更少的 copy 操作。即可以将一类的连续的 struct 动态的覆盖式的加入原数组，只有第二类需要加入辅助数组。辅助数组的大小仅为 \max(2m,n)。

原本我们每一层都要进行 2len 的复制操作。现在平 均仅需要 1.5len 次。

因此数组总大小为 2n+4m，且每个 struct 需要存三个数，空间开销为普通整体二分的 \dfrac 3 5\times \dfrac 6 5=0.72 倍。更好的一件事是辅助数组平均造成的空间开销为 m，即空间开销为普通整体二分的 0.6 倍。事实上测试结果更加接近 平均情况。

https://www.luogu.com.cn/record/51628699

#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
    int l,k,w;
    friend bool operator <(const node &x,const node &y)
    {
        return x.w<y.w;
    }
}q[600005],q2[400005];
int ans[200005];
int h[200005],a[200005];
int anss[200005];
bool cmp(const node &x,const node &y)
{
    return x.l<y.l;
}
void solve(int l,int r,int L,int R,int L2,int R2)
{
    if(L>R||L2>R2) return;
    if(l==r)
    {
        for(;L2<=R2;L2++)
            if(q[L2].w>0)
                ans[q[L2].w]=l;
        return;
    }
    int i,j=L,mid=l+r>>1,cnt1=L-1,cnt2=0,cnt3=L2-1,x;
    for(i=L;i<=R;i++)
    {
        if(q[i].l<=mid) q[++cnt1]=q[i];
        else q2[++cnt2]=q[i];
    }
    for(i=1;i<=cnt2;i++)
        q[cnt1+i]=q2[i];
    cnt2=0;
    for(i=L2;i<=R2;i++)
    {
        for(;j<=cnt1&&q[i].l>=q[j].w;j++);
        if(q[i].w>0)
            anss[q[i].w]+=j-L;  
        else
            anss[-q[i].w]-=j-L;
    }
    for(i=L2;i<=R2;i++)
    {
        if(q[i].w>0)
            x=anss[q[i].w],anss[q[i].w]=0;
        else
            x=anss[-q[i].w];
        if(q[i].k<=x)
            q[++cnt3]=q[i];
        else
            q[i].k-=x,q2[++cnt2]=q[i];  
    }
    for(i=1;i<=cnt2;i++)
        q[cnt3+i]=q2[i];
    solve(l,mid,L,cnt1,L2,cnt3);
    solve(mid+1,r,cnt1+1,R,cnt3+1,R2);
}
inline int read()
{
   register int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main()
{
    int i,cnt,m,le,l,r,k;
    cnt=n=read(),m=read();
    for(i=1;i<=n;i++)
        h[i]=a[i]=read();
    sort(h+1,h+1+n);
    le=unique(h+1,h+1+n)-h;
    for(i=1;i<=n;i++)
        q[i]=node({int(lower_bound(h+1,h+le,a[i])-h),0,i});
    for(i=1;i<=m;i++)
    {
        l=read(),r=read(),k=read();
        q[++cnt].l=l-1,q[cnt].k=k,q[cnt].w=-i;
        q[++cnt].l=r,q[cnt].k=k,q[cnt].w=i;
    }
    sort(q+1,q+1+n);
    sort(q+n+1,q+cnt+1,cmp);
    solve(1,le-1,1,n,n+1,cnt);
    for(i=1;i<=m;i++)
        printf("%d\n",h[ans[i]]);
}