求区间第 k 大值的若干方法

Wangxun · 2023-01-28 19:14:48 · 个人记录

首先，感谢 OJ 上的 n,m \le 30000 的限制，让方法如此丰富多彩！

进阶版本

• 可持久化线段树

又叫主席树。

就是把一颗线段树添加一条链的节点，建成另一颗线段树，查询 [l,r] 就是把以 rt_r 为根的线段树“减去”以 rt_{l-1} 为根的线段树。

在线算法，不支持修改。

时间复杂度 O(n \log n) 达到最低，代码量也小，但初学者存在一定思维难度。

拓展阅读：Oi Wiki 可持久化线段树

代码：

#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define N 30010
int a[N],b[N],rt[N],n,m,k;
struct Seg
{
    #define mid (l+r)/2
    int sum[N<<4],L[N<<4],R[N<<4],times; 
    Seg()
    {
        memset(sum,0,sizeof(sum));
        times = 0;  
    }
    int update(int u,int v,int l,int r,int x)
    {
        if(!u) u = ++times;
        sum[u] = sum[v] + 1;
        if(l == r) return u;
        if(x <= mid) L[u] = update(L[u],L[v],l,mid,x),R[u] = R[v];
        else R[u] = update(R[u],R[v],mid+1,r,x),L[u] = L[v];
        return u;
    }
    int query(int u,int v,int l,int r,int t)
    {
        if(l == r) return l;
        if(sum[R[v]] - sum[R[u]] >= t) return query(R[u],R[v],mid+1,r,t);
        return query(L[u],L[v],l,mid,t-(sum[R[v]]-sum[R[u]]));
    }
}tree;
int main()
{   
    scanf("%d%d",&n,&m);
    F(i,1,n) scanf("%d",&a[i]),b[i] = a[i];
    sort(&b[1],&b[n+1]);
    k = unique(&b[1],&b[n+1]) - &b[1];
    F(i,1,n)
    {
        a[i] = lower_bound(&b[1],&b[k+1],a[i]) - b;
        rt[i] = tree.update(rt[i],rt[i-1],1,k,a[i]);
    }
    while(m--)
    {
        int l,r,t;
        scanf("%d%d%d",&l,&r,&t);
        printf("%d\n",b[tree.query(rt[l-1],rt[r],1,k,t)]);  
    }
    return 0;
}

• 莫队 + 线段树（建议尝试）

观察可以发现，这题的区间是可以移动的，加减一个数用权值线段树维护只有 O(\log n) 的时间复杂度，那莫队就呼之欲出了。

莫队是一种离线算法，是对一些 [l,r] 进行分块排序，可以证明能使时间复杂度达到 O(n \sqrt{n})。

if(X.l/s == Y.l/s) return X.r < Y.r;
return X.l < Y.l;   

其中 s \leftarrow \frac{n}{\sqrt{m}}。

时间复杂度 O(m \sqrt{n} \log{n})。

代码：

#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define N 30010
int a[N],b[N],ans[N],n,m,s,k;
struct node
{
    int l,r,t,id;
    inline bool friend operator<(const node &X,const node &Y)
    {
        if(X.l/s == Y.l/s) return X.r < Y.r;
        return X.l < Y.l;   
    } 
}p[N];
struct Seg
{
    #define mid (l+r)/2
    #define ls u<<1
    #define rs u<<1|1
    int sum[N<<2];
    Seg()
    {
        memset(sum,0,sizeof(sum));
    }
    inline void pushup(int u)
    {
        sum[u] = sum[ls] + sum[rs];
    }
    void update(int u,int l,int r,int x,int y)
    {
        if(l == r)
        {
            sum[u] += y;
            return;
        }
        if(x <= mid) update(ls,l,mid,x,y);
        else update(rs,mid+1,r,x,y);
        pushup(u);
    }
    int query(int u,int l,int r,int t)
    {
        if(l == r) return l;
        if(t <= sum[rs]) return query(rs,mid+1,r,t);
        return query(ls,l,mid,t-sum[rs]);
    }
}tree;
int main()
{   
    scanf("%d%d",&n,&m);
    s = sqrt(n); 
    F(i,1,n) scanf("%d",&a[i]),b[i] = a[i];
    sort(&b[1],&b[n+1]);
    k = unique(&b[1],&b[n+1]) - &b[1];
    F(i,1,n) a[i] = lower_bound(&b[1],&b[k+1],a[i]) - b;
    F(i,1,m)
    {
        scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].t);
        p[i].id = i;
    }
    sort(&p[1],&p[m+1]);
    int l = 1,r = 0;
    F(i,1,m)
    {
        while(r < p[i].r) tree.update(1,1,k,a[++r],1);
        while(r > p[i].r) tree.update(1,1,k,a[r--],-1);
        while(l < p[i].l) tree.update(1,1,k,a[l++],-1);
        while(l > p[i].l) tree.update(1,1,k,a[--l],1);
        ans[p[i].id] = b[tree.query(1,1,k,p[i].t)];
    }
    F(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

• 整体二分

当当当当！

先考虑对单个询问进行二分。

我们二分答案为 p，判断大于等于 p 的是否达到了 k 个，如果达到了，答案大于等于 k；否则，答案小于 k。

但这样明显会超时，于是采用整体二分。

我们二分所有的询问，对其进行“分流”（就像高考一样），对于满足一定条件的询问，逐渐缩小二分的范围，直到 l=r，就是答案。

至于如何判断，使用树状数组进行维护即可，注意每次清空不能直接 memset，会超时，应当一个一个地清空。

顺便提一句，这种方法是可以支持修改！（但必须离线）

时间复杂度：O(n \log^{2}{n})。

代码：

#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define N 30010
int a[N],b[N],ans[N],n,m;
struct node
{
    int l,r,t,id; 
};
vector<node> q;
vector<int> g[N];
struct Tree
{
    int sum[N];
    Tree() 
    {
        memset(sum,0,sizeof(sum));
    }
    inline void update(int x,int y)
    {
        while(x <= n)
        {
            sum[x] += y;
            x += x & -x;
        }
    }
    inline int query(int x)
    {
        int ret = 0;
        while(x)
        {
            ret += sum[x];
            x -= x & -x;
        }
        return ret;
    }
}tree;
void solve(int l,int r,vector<node> h)
{
    if(l == r)
    {
        for(auto v:h) ans[v.id] = b[l];
        return;
    }
    int mid = (l + r) >> 1;
    F(i,mid+1,r)
        for(auto j:g[i])
            tree.update(j,1);
    vector<node> h1,h2;
    for(auto v:h)
    {
        int now = tree.query(v.r) - tree.query(v.l-1);
        if(now >= v.t) h2.push_back(v);
        else h1.push_back((node){v.l,v.r,v.t-now,v.id}); 
    }
    F(i,mid+1,r)
        for(auto j:g[i])
            tree.update(j,-1);
    solve(l,mid,h1);
    solve(mid+1,r,h2);
}
int main()
{   
    scanf("%d%d",&n,&m);
    F(i,1,n) scanf("%d",&a[i]),b[i] = a[i];
    sort(&b[1],&b[n+1]);
    int k = unique(&b[1],&b[n+1]) - &b[1];
    F(i,1,n) a[i] = lower_bound(&b[1],&b[k+1],a[i]) - b,g[a[i]].push_back(i);
    F(i,1,m)
    {
        node p;
        scanf("%d%d%d",&p.l,&p.r,&p.t);
        p.id = i;
        q.push_back(p); 
    }
    solve(1,k,q);
    F(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

带修改的整体二分

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(register T &x)
{
    register T p = 1,num = 0;
    char c = getchar();
    while(c < '0'||c > '9')
    {
        if(c == '-') p = -p;
        c = getchar();
    }
    while('0' <= c&&c <= '9')
    {
        num = (num<<3)+(num<<1)+(c^48);
        c = getchar();
    }
    x = p * num;
}
template<typename T>inline void write(register T x)
{
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) write(x/10);
    putchar(x%10+48);
}
#define D(i,a,b) for(register int i=a;i>=b;--i)
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define pii pair<int,int>
#define N 100010
struct node
{
    int id,l,r,k;
    //id == 0 l = position r = ±1 k = number 
    //id > 0 find kth number in [l,r]
}Q[N],q[N<<1],q1[N<<1],q2[N<<1];
int ans[N],d[N*3],len,n,m,p,a[N],t;
struct Tree
{
    int sum[N];
    inline void update(int x,int y)
    {
        while(x <= n)
        {
            sum[x] += y;
            x += x & -x;
        }
    }
    inline int query(int x)
    {
        int ret = 0;
        while(x)
        {
            ret += sum[x];
            x -= x & -x;
        }
        return ret;
    }
}tree;
void solve(int L,int R,int l,int r)
{
    if(L > R) return;
    if(l == r)
    {
        F(i,L,R)
            if(q[i].id) 
                ans[q[i].id] = l;
        return;
    } 
    int mid = (l + r) >> 1,cnt1 = 0,cnt2 = 0;
    F(i,L,R)
    {
        if(q[i].id) 
        {
            int tp = tree.query(q[i].r) - tree.query(q[i].l-1);
            if(tp >= q[i].k) q1[++cnt1] = q[i];
            else q2[++cnt2] = q[i],q2[cnt2].k -= tp; 
        }
        else
        { 
            if(q[i].k <= mid) tree.update(q[i].l,q[i].r),q1[++cnt1] = q[i];
            else q2[++cnt2] = q[i]; 
        }
    }
    F(i,L,R) 
        if(!q[i].id&&q[i].k <= mid)
            tree.update(q[i].l,-q[i].r);
    F(i,L,R)
    {
        if(i-L+1 <= cnt1) q[i] = q1[i-L+1];
        else q[i] = q2[i-L-cnt1+1];
    }
    solve(L,L+cnt1-1,l,mid);
    solve(L+cnt1,R,mid+1,r);
}
int main()
{
    while(~scanf("%d",&n))
    {
        len = p = t = 0;
        F(i,1,n) read(a[i]),d[++len] = a[i];
        read(m);
        F(i,1,m)
        {
            read(Q[i].id);
            if(Q[i].id == 2) read(Q[i].l),read(Q[i].r),read(Q[i].k);
            else
            {
                read(Q[i].l),read(Q[i].r);
                d[++len] = Q[i].r;
            }
        }
        sort(&d[1],&d[len+1]);
        len = unique(&d[1],&d[len+1]) - &d[1];
        F(i,1,n)
        {
            a[i] = lower_bound(&d[1],&d[len+1],a[i]) - d;
            q[++p] = (node){0,i,1,a[i]};
        }
        F(i,1,m)
        {
            if(Q[i].id == 2) q[++p] = (node){++t,Q[i].l,Q[i].r,Q[i].k};
            else 
            {
                q[++p] = (node){0,Q[i].l,-1,a[Q[i].l]};
                a[Q[i].l] = lower_bound(&d[1],&d[len+1],Q[i].r) - d;
                q[++p] = (node){0,Q[i].l,1,a[Q[i].l]};  
            }   
        }
        solve(1,p,1,len);
        F(i,1,t) write(d[ans[i]]),putchar('\n');    
    }
    return 0;
}

• 树套树

选择的是外层树状数组套主席树。

这种方法可以方便地支持修改。

注意要将 \log n 颗线段树记录下来一起递归。

时间复杂度：O(n \log^{2}{n})。

代码：

#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define N 30010
int n,m,k,a[N],b[N],rt[N],len;
pair<int,int> g[N];
struct Seg
{
    #define mid (l+r)/2
    int sum[N<<8],L[N<<8],R[N<<8],times;
    Seg()
    {
        times = 0;
        memset(sum,0,sizeof(sum));
    }
    int update(int u,int l,int r,int x)
    {
        if(!u) u = ++times; 
        ++sum[u];
        if(l == r) return u;
        if(x <= mid) L[u] = update(L[u],l,mid,x);
        else R[u] = update(R[u],mid+1,r,x);
        return u;
    }
    int query(int l,int r,int t)
    {
        if(l == r) return l;
        int ret = 0;
        F(i,1,len) ret += g[i].second * sum[R[g[i].first]]; 
        if(t <= ret) 
        {
            F(i,1,len) g[i] = (pair<int,int>){R[g[i].first],g[i].second};
            return query(mid+1,r,t);    
        }
        F(i,1,len) g[i] = (pair<int,int>){L[g[i].first],g[i].second};
        return query(l,mid,t-ret);
    }
}tr;
struct Tree
{
    inline void update(int x,int y)
    {
        while(x <= n)
        {
            rt[x] = tr.update(rt[x],1,k,y);
            x += x & -x;
        }
    }
    inline int query(int l,int r,int t)
    {
        len = 0;
        while(r)
        {
            g[++len] = {rt[r],1};
            r -= r & -r;    
        }       
        --l;
        while(l)
        {
            g[++len] = {rt[l],-1};
            l -= l & -l;
        }
        return b[tr.query(1,k,t)];
    } 
}tree;
int main()
{   
    scanf("%d%d",&n,&m);
    F(i,1,n) scanf("%d",&a[i]),b[i] = a[i];
    sort(&b[1],&b[n+1]);
    k = unique(&b[1],&b[n+1]) - &b[1];
    F(i,1,n) a[i] = lower_bound(&b[1],&b[k+1],a[i]) - b,tree.update(i,a[i]);
    while(m--)
    {
        int l,r,t;
        scanf("%d%d%d",&l,&r,&t);
        printf("%d\n",tree.query(l,r,t));
    }
    return 0;
}