浅谈第k大

FxorG · 2021-06-18 21:33:30 · 个人记录

由于我比较菜，所以有什么错误请尽管提出，感谢！

什么是第k大？

就是把一段序列按从小到大排序，下标规定从1开始，下标为k的数即为此段序列的第k大。

如何解决？

下文中将使用长度为 n 的 a 序列，数列最大值为 V ，并用 O()-O()-O() 表示预处理时间复杂度，单次查询时间复杂度，空间复杂度。

1.一个 naive 的想法，使用 sort 使数组有序，然后输出下标为 k 的数。显然，这样做的复杂度是 O(1)-O(n \log n)-O(n) 的。

2.我们发现，我们并不需要整个数组有序，只找出第k大就好了，那么可以利用快速排序分治的思想，每次递归中随机选取一个数记为 pos ，将序列分为 3 段，即 [l,pos-1],[pos,pos],[pos+1,r] 使得第一段的数均小于 a[pos] ，第三段的数均大于 a[pos] ，判断下 pos 是否等于 k 即可。

• 复杂度为 O(1)-O(n)-O(n).

• 值得注意的是，STL 中 nth \_element 可以直接使用。

• 代码（引用自oi-wiki）

  // 模板的T参数表示元素的类型，此类型需要定义小于（<）运算
  template <typename T>
  // arr为查找范围数组，rk为需要查找的排名（从0开始），len为数组长度
  T find_kth_element(T arr[], int rk, const int len) {
  if (len <= 1) return arr[0];
  // 随机选择基准（pivot）
  const T pivot = arr[rand() % len];
  // i：当前操作的元素
  // j：第一个等于pivot的元素
  // k：第一个大于pivot的元素
  int i = 0, j = 0, k = len;
  // 完成一趟三路快排，将序列分为：小于pivot的元素 ｜ 等于pivot的元素 ｜
  // 大于pivot的元素
  while (i < k) {
  if (arr[i] < pivot)
    swap(arr[i++], arr[j++]);
  else if (pivot < arr[i])
    swap(arr[i], arr[--k]);
  else
    i++;
  }
  // 根据要找的排名与两条分界线的位置，去不同的区间递归查找第k大的数
  // 如果小于pivot的元素个数比k多，则第k大的元素一定是一个小于pivot的元素
  if (rk < j) return find_kth_element(arr, rk, j);
  // 否则，如果小于pivot和等于pivot的元素加起来也没有k多，则第k大的元素一定是一个大于pivot的元素
  else if (rk >= k)
  return find_kth_element(arr + k, rk - k, len - k);
  // 否则，pivot就是第k大的元素
  return pivot;
  }

3.我们又有一个 navie 的想法，我们可以开个桶去记录啊！然后暴力枚举 [1,V] 的数，开个 res 累计下数量是否到 k 即可。显然，这样复杂度是 O(n)-O(V)-O(V) 的。

4.我们发现，我们桶的思想就是枚举到 i 时，知道了小于等于 i 的数的数量，并判断这个数量是否大于等于k。

• 于是，我们得到，假如一个数是第 k 大，那么一定至少有 k 个数小于等于它。那么我们只需要找出第一个满足这个条件的数即可。

• 我们发现这满足单调性，因为假如 2 数 i,j,(i<j)，满足有 k 个数小于等于 i ，那么必定有 k 个数小于等于 j 。

• 对于快速求出小于等于某一个数的数量，我们可以使用值域树状数组，对于寻找这个数，我们可以二分。

• 复杂度为 O(n \log V)-O(log^2V)-O(V)

• 对于值域过大的时候可以考虑动态开点树状数组，开个 map 记录需要用到的 id 即可。

5.对顶堆

• 我们分别开一个大根堆和一个小根堆，那么有个很好的性质：假如大根堆的堆顶小于小根堆堆顶，那么大根堆中的所有元素都小于小根堆中的所有元素。

• 这启发我们可以限制大根堆的 size=k 。

• 那么我们可以先往大根堆 push 前 k 个元素，之后对于一个元素，假如大于大根堆堆顶，就进去小根堆，否则大根堆弹出堆顶，然后再进去大根堆，可以知道第k大即为最后大根堆堆顶。

• 不过这个东西的局限性比较大，只能适用于前缀区间的第k大，所以复杂度只讨论单次的查询，即为 O(\log n).

6.权值线段树

• 既然有了权值树状数组，那么肯定也有权值线段树。

• 我们对于一个数 a[i] ，将线段树的 [a[i],a[i]]+1 ，当查询第k大时，因为 左子树所有的值都小于右子树 所以我们可以判断左子树的 size 是否大于k，是递归左子树；不是，将 k-=size[left \_son] 之后递归右子树。 直至递归到叶子节点时，答案即为当前值。

• 注意特判下 k > size[root] 的情况。

• 复杂度 O(n \log V)-O(\log V)-O(4V)，这里认为先 build 整个序列，但需要注意的是，单靠权值线段树无法做到区间第 k 大。

7.平衡树

• 详见模板题

• 复杂度 O(n \log n)-O(\log n)-O(n)，使用平衡树时需要考虑常数带来的影响。

• 这里推荐一种比较好写的平衡树，可以用 01-trie 去代替，因为 01-trie 有一个性质，即左子树的点都比右子树小，所以可以仿照权值线段树的查询方式，对于区间第 k 大上可持久化即可，代码编写难度不高。

8.序列分块套二分（支持区间第 k 大）

• 我们可以块内维护有序序列，然后对于查询 [l,r] 中有多少个数小于等于 x 时，我们可以散块暴力，整块 upper\_bound ，并记录块内 max 与 min 减小常数即可。

• 显然复杂度为 O(n \sqrt{n \log n})-O(\log V \sqrt{n \log n}) - O(n).

• 模板.

9.值域分块套序列分块（支持区间第 k 大）

• 对于分块来说，应该能省一个 log 就省掉，在 V 与 n 同阶时，我们可以考虑以下做法。

• 维护 cnt1[i][j] 表示第 i 块值域在第 j 块的个数前缀和， cnt2[i][j] 维护第 j 块值为 j 的个数前缀和。

• 对于查找，我们应该先统计出散块的贡献，然后先确定答案所在值域的块，之后再在值域块内查找。

• 这样子复杂度就做到了 O(V\sqrt{n})-O(\sqrt{V})-O(V\sqrt{n}).

• 模板

• 但对于这题的修改操作，我们还需要开一个并查集，对于相同值的指向同一个根并记录每个点的根，然后修改时更改这个根的值即可。 push\_down 时将每个点的值设为并查集所指向的根节点的权值。

• 值得注意的是，这个东西可以再用块状链表每个块的位置关系，然后暴力找出操作左右块，其他类似于上述的即可维护，做到可插入。

10.主席树（静态区间第 k 大）

• 显然，权值线段树缺点就是无法知道区间的权值线段树长什么样。对此，我们可以利用前缀和。即 [l,r] 的权值线段树等于 [1,r] 的减去 [1,l-1] 的。

• 如何维护前缀权值线段树？假设黑色点为原树，红色点为新树，new 点为改变的叶子结点。我们可以发现，新树在原树上就改变了一个点，那么对于没有改变的左右子树，我们可以直接从原树转移，对于改变了，开新点然后权值加上即可，这里注意要动态开点才能保证空间复杂度正确。

• 模板

• 复杂度 O(n \log V)-O(log V)-O(n \log n)

11.树套树（动态区间第k大）

• 我们发现，修改后我们需要快速维护前缀和，假如暴力维护的话复杂度单次会 O(n)，于是我们上个树状数组，每次修改 \log n 棵权值线段树，查询时也查询 \log n 棵权值线段树，得到 [l,r] 的 size.

• 模板.

• 复杂度 O(n \log n \log V)-O(\log n \log V)-O(n \log n \log V).

• 其实不止树状数组套线段树，还有线段数套线段树，线段树套平衡树。线段数套平衡树.

12.整体二分（离线，动态区间第k大）

• 还是回到4，我们发现我们要是能把所有操作都整合在一起就好了。

• 我们先考虑不带修。

• 假如我们现在值域遍历到 [l,r] ，答案在这个区间的询问区间为 [L,R]，那么我们可以设定 mid，对于权值小于等于 mid 的先全部加入，再对于每一个询问判断答案是否在 [1,mid] 之中还是 [mid+1,r] 之中，这个可以通过树状数组来查询值域在 [1,mid] 中且序列在 [query\_l,query\_r] 之中的个数（因为在树状数组里面的都是值域 [1,mid] 的，所以只要查在查询区间里的即可）。

• 对于询问可以划分为答案在值域在左子树的和右子树的，递归到叶子即为所有询问的答案。

• 考虑带修，我们对于每一个点记录 pre[i] 表示之前存的值，令 (x,w) 为对答案贡献 w*x，添加操作 (pre[i],-1) 与 (new,1) 即可。

• mcyl35大佬的优化

13.莫队维护区间树状数组做到区间第k大 （离线）

• 字面意思，处理好区间值域树状数组的时候二分答案即可。

• 我们用离散化就能轻松做到O(m \log m)-O(\sqrt{n}\log n)-O(n)

• 好处也可能就是比较好写且空间较小，代码在后面会有，竟然能跑过主席树的模板？！

接下来是一些奇怪的第 k 大。

1.矩阵第 k 大

• 我们是可以先对整个矩阵的值从小到大排序，之后整体二分套二维树状数组查询即可。

2.树上路径第 k 大

• 还是整体二分，对于查询多少个数在这个序列范围上树剖大力维护每条重链上的贡献即可。

Code:

• 8

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>

#define N (int)(1e5+5)
#define SN (int)(1e3+5)
#define il inline
#define fp(i,qaq,qwq) for(int i=(qaq);i<=(qwq);++i)
#define fd(i,qaq,qwq) for(int i=(qaq);i>=(qwq);--i)
#define id(xgf) ((xgf-1)/blk+1)

using namespace std;

int b[SN][SN],cnt[SN],tag[SN],a[N],gr[SN][2];
int n,m,blk;

il int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) {
        sum=(sum<<3)+(sum<<1)+ch-'0';
        ch=getchar();
    }
    return sum*f;
}

il void pr(int x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}

il void reset(int x) {
    cnt[x]=0;
    fp(i,gr[x][0],gr[x][1]) b[x][cnt[x]++]=a[i];
    sort(b[x],b[x]+cnt[x]);
}

il void update(int x,int y,int z) {
    if(id(x)==id(y)) {
        fp(i,x,y) a[i]+=z;
        reset(id(x));
    } else {
        fp(i,x,gr[id(x)][1]) a[i]+=z;
        reset(id(x));
        fp(i,id(x)+1,id(y)-1) tag[i]+=z;
        fp(i,gr[id(y)][0],y) a[i]+=z;
        reset(id(y));
    }
}

il int get_ans(int x,int y,int z) {
    if(id(x)==id(y)) {
        int tot=0;
        fp(i,x,y) if(a[i]+tag[id(x)]<=z) ++tot;
        return tot;
    } else {
        int tot=0;
        fp(i,x,gr[id(x)][1]) if(a[i]+tag[id(x)]<=z) ++tot;
        fp(i,gr[id(y)][0],y) if(a[i]+tag[id(y)]<=z) ++tot;
        fp(i,id(x)+1,id(y)-1) tot+=(b[i][cnt[i]-1]+tag[i])<=z?cnt[i]:(b[i][0]+tag[i]>z)?0:upper_bound(b[i],b[i]+cnt[i],z-tag[i])-b[i];
        return tot;
    }
}

il int qry(int x,int y,int z) {
    int answ=-1,l=-2e9,r=(int)(2e9);
    while(l<=r) {
        int mid=(l+r)>>1;
        if(get_ans(x,y,mid)>=z) answ=mid,r=mid-1;
        else l=mid+1;
    }
    return answ;
}

signed main() {
    n=rd(); m=rd(); blk=pow(n*log(n),0.425);
    int op,x,y,z,tmp=-1;
    fp(i,1,n) {
        a[i]=rd();
        if(id(i)!=tmp) gr[id(i)][0]=i,tmp=id(i);
        else gr[id(i)][1]=i;
        b[id(i)][cnt[id(i)]++]=a[i];
    }
    fp(i,1,id(n)) sort(b[i],b[i]+cnt[i]);
    fp(i,1,m) {
        op=rd(); x=rd(); y=rd(); z=rd();
        if(op==1) {
            pr(qry(x,y,z));
            puts("");
        } else {
            update(x,y,z);
        }
    }
    return 0;
}

• 9

#include <bits/stdc++.h>

#define N (int)(1e5+20)
#define M 320

using namespace std;

int n,m,sz,bl[N],a[N],L[M],R[M],cnt1[M][M],cnt2[M][N],sum1[M],sum2[N],id[M][N],rid[M][N],pos[N];

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

void pr(int x) {
    if(x<0) {putchar('-');x=-x;}
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}

void build(int x) {
    int tot=0;
    for(int i=1;i<=sz;i++) id[x][rid[x][i]]=0;
    for(int i=L[x];i<=R[x];i++) {
        if(!id[x][a[i]]) id[x][a[i]]=++tot,rid[x][tot]=a[i];
        pos[i]=id[x][a[i]];
    }
}

void push_down(int x) {
    for(int i=L[x];i<=R[x];i++) a[i]=rid[x][pos[i]]; 
}

void solve(int l,int r,int x,int y) {
    for(int i=l;i<=r;i++) {
        if(a[i]==x) {
            --cnt1[bl[l]][bl[x]]; --cnt2[bl[l]][x];
            ++cnt1[bl[l]][bl[y]]; ++cnt2[bl[l]][y];
            a[i]=y;
        }
    }
}

void update(int l,int r,int x,int y) {
    if(x==y||cnt2[bl[r]][x]-cnt2[bl[l]-1][x]==0) return;
    for(int i=bl[n];i>=bl[l];i--) cnt2[i][x]-=cnt2[i-1][x],cnt2[i][y]-=cnt2[i-1][y],cnt1[i][bl[x]]-=cnt1[i-1][bl[x]],cnt1[i][bl[y]]-=cnt1[i-1][bl[y]];
    if(bl[l]==bl[r]) {
        push_down(bl[l]);
        solve(l,r,x,y);
        build(bl[l]);
    } else {
        push_down(bl[l]); push_down(bl[r]);
        solve(l,R[bl[l]],x,y); solve(L[bl[r]],r,x,y);
        build(bl[l]); build(bl[r]);
        for(int i=bl[l]+1;i<bl[r];i++) {
            if(!cnt2[i][x]) continue;
            if(cnt2[i][y]) {
                push_down(i);
                solve(L[i],R[i],x,y);
                build(i);
            } else {
                cnt1[i][bl[y]]+=cnt2[i][x]; cnt1[i][bl[x]]-=cnt2[i][x];
                cnt2[i][y]=cnt2[i][x]; cnt2[i][x]=0;
                id[i][y]=id[i][x]; rid[i][id[i][x]]=y; id[i][x]=0;
            }
        }
    }
    for(int i=bl[l];i<=bl[n];i++) cnt2[i][x]+=cnt2[i-1][x],cnt2[i][y]+=cnt2[i-1][y],cnt1[i][bl[x]]+=cnt1[i-1][bl[x]],cnt1[i][bl[y]]+=cnt1[i-1][bl[y]];
}

int kth(int l,int r,int k) {
    int sum=0;
    if(bl[l]==bl[r]) {
        push_down(bl[l]);
        for(int i=l;i<=r;i++) sum2[i]=a[i];
        nth_element(sum2+l,sum2+l+k-1,sum2+r+1); int answ=sum2[l+k-1];
        for(int i=l;i<=r;i++) sum2[i]=0;
        return answ;
    }
    push_down(bl[l]); push_down(bl[r]);
    for(int i=l;i<=R[bl[l]];i++) ++sum1[bl[a[i]]],++sum2[a[i]];
    for(int i=L[bl[r]];i<=r;i++) ++sum1[bl[a[i]]],++sum2[a[i]];
    for(int i=1;i<=(N-1)/sz+1;++i) {
        if(sum+sum1[i]+cnt1[bl[r]-1][i]-cnt1[bl[l]][i]>=k){
            for(int j=(i-1)*sz+1;j<=i*sz;++j)
                if(sum+sum2[j]+cnt2[bl[r]-1][j]-cnt2[bl[l]][j]>=k){
                    for(int o=l;o<=R[bl[l]];++o) --sum1[bl[a[o]]],--sum2[a[o]];
                    for(int o=L[bl[r]];o<=r;++o) --sum1[bl[a[o]]],--sum2[a[o]]=0;
                    return j;
                }
                else sum+=sum2[j]+cnt2[bl[r]-1][j]-cnt2[bl[l]][j];
        }
        else sum+=sum1[i]+cnt1[bl[r]-1][i]-cnt1[bl[l]][i];
    }
}

int main() {
    n=rd(); m=rd(); sz=sqrt(n);
    for(int i=1;i<N;i++) bl[i]=(i-1)/sz+1;
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=bl[n];i++) L[i]=(i-1)*sz+1,R[i]=i*sz; R[bl[n]]=n;
    for(int i=1;i<=bl[n];i++) build(i);
    for(int x=1;x<=bl[n];x++) {
        for(int i=1;i<=bl[N-1];i++) cnt1[x][i]=cnt1[x-1][i];
        for(int i=1;i<N;i++) cnt2[x][i]=cnt2[x-1][i];
        for(int i=L[x];i<=R[x];i++) ++cnt1[x][bl[a[i]]],++cnt2[x][a[i]];
    }
    int op,l,r,x,y;
    while(m--) {
        op=rd(); l=rd(); r=rd(); x=rd();
        if(op==1) y=rd(),update(l,r,x,y);
        else pr(kth(l,r,x)),puts("");
    }
    return 0;
}

• P4278 带插入区间K小值

#include <bits/stdc++.h>

#define N (int)(7e4+5)
#define M 1000
#define ED puts("")
#define il inline
il int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

il void pr(int x) {
    if(x<0) {putchar('-');x=-x;}
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}

char nex() {
    char ch=getchar();
    while(!isalpha(ch)) ch=getchar();
    return ch;
}

using namespace std;

struct node {
    int l,r,sz,cnt1[M],cnt2[N],a[M];
    int& operator [](const int k) {
        return a[k];
    }
}g[M];

int id[N],sum1[M],sum2[N];
int n,m,bl,tot;

il int kth(int l,int r,int k) {
    int lb,rb,no=1,qwq=1,res=0;
    while(g[no].sz<l) l-=g[no].sz,no=g[no].r;
    lb=no; no=1;
    while(g[no].sz<r) r-=g[no].sz,no=g[no].r;
    rb=no;
    //cout<<l<<" "<<r<<" "<<k<<" "<<lb<<" this is question "<<rb<<endl;
    if(lb==rb) {
        for(int i=l;i<=r;i++) {
            ////cout<<val[lb][i]<<" ";
            ++sum1[id[g[lb][i]]],++sum2[g[lb][i]];
        }
        qwq=1;
        while(sum1[qwq]<k) k-=sum1[qwq],++qwq;
        qwq=(qwq-1)*bl; //cout<<qwq<<endl;
        while(sum2[qwq]<k) k-=sum2[qwq],++qwq; 
        for(int i=l;i<=r;i++) sum1[id[g[lb][i]]]=0,sum2[g[lb][i]]=0;
        return qwq;
    }
    qwq=1;
    for(int i=l;i<=g[lb].sz;i++) {
        ++sum1[id[g[lb][i]]],++sum2[g[lb][i]];
    }
    for(int i=1;i<=r;i++) ++sum1[id[g[rb][i]]],++sum2[g[rb][i]];
    while(sum1[qwq]+g[g[rb].l].cnt1[qwq]-g[lb].cnt1[qwq]<k) {
        k-=sum1[qwq]+g[g[rb].l].cnt1[qwq]-g[lb].cnt1[qwq]; ++qwq;
    }
    qwq=(qwq-1)*bl; //cout<<qwq<<endl;
    while(sum2[qwq]+g[g[rb].l].cnt2[qwq]-g[lb].cnt2[qwq]<k) {
        k-=sum2[qwq]+g[g[rb].l].cnt2[qwq]-g[lb].cnt2[qwq]; ++qwq;
    }
    for(int i=l;i<=g[lb].sz;i++) --sum1[id[g[lb][i]]],--sum2[g[lb][i]];
    for(int i=1;i<=r;i++) --sum1[id[g[rb][i]]],--sum2[g[rb][i]];
    return qwq;
}

il void update(int x,int v) {
//  //cout<<x<<" "<<v<<endl;
    int b,no=1,pre_v;
    while(g[no].sz<x) {
        x-=g[no].sz,no=g[no].r;
//      //cout<<x<<" "<<no;
    }
    b=no; pre_v=g[b][x];
    if(pre_v==v) return;
    g[b][x]=v;
    for(int i=b;i;i=g[i].r) {
        --g[i].cnt1[id[pre_v]]; --g[i].cnt2[pre_v];
        ++g[i].cnt1[id[v]]; ++g[i].cnt2[v];
    }
}

il void split(int x) {
    int b=++tot;
    g[b].r=g[x].r; g[g[x].r].l=b; g[x].r=b; g[b].l=x;
    g[b].sz=g[x].sz/2;
    int tmp=g[x].sz-g[b].sz;
    memcpy(g[b].cnt1,g[x].cnt1,sizeof(g[x].cnt1));
    memcpy(g[b].cnt2,g[x].cnt2,sizeof(g[x].cnt2));
    for(int i=tmp+1;i<=g[x].sz;i++) {
        g[b][i-tmp]=g[x][i];
        --g[x].cnt1[id[g[x][i]]]; --g[x].cnt2[g[x][i]];
        g[x][i]=0;
    }
    g[x].sz=tmp;
}

il void insert(int x,int v) {
    int b,no=1;
    while(g[no].sz<x) {
        if(g[no].r) x-=g[no].sz,no=g[no].r;
        else break;
    }
    b=no; //cout<<b<<endl;
    for(int i=g[b].sz;i>=x;i--) g[b][i+1]=g[b][i];
    g[b][x]=v; ++g[b].sz;
    for(int i=b;i;i=g[i].r) {
        ++g[i].cnt1[id[v]]; ++g[i].cnt2[v];
    }
    if(g[b].sz>2*bl) split(b);
}

int main() {
    char op; int x,y,z,las=0;
    n=rd(); bl=400; 
    for(int i=0;i<=N-5;i++) id[i]=i/bl+1; tot=id[n];
    for(int i=1;i<=n;i++) x=rd(),g[id[i]][++g[id[i]].sz]=x;
    m=rd();
    for(int i=1;i<=id[n];i++) g[i].l=i-1,g[i].r=i+1; g[1].l=g[id[n]].r=0;
    for(int x=1;x<=id[n];x++) {
        for(int i=1;i<=g[x].sz;i++) ++g[x].cnt1[id[g[x][i]]],++g[x].cnt2[g[x][i]];
        for(int i=0;i<=N-5;i++) {
            if(!i||id[i]!=id[i-1]) g[x].cnt1[id[i]]+=g[x-1].cnt1[id[i]];
            g[x].cnt2[i]+=g[x-1].cnt2[i];
        }
    }   
    while(m--) {
        op=nex();
        if(op=='Q') {
            x=rd()^las; y=rd()^las; z=rd()^las;
            pr(las=kth(x,y,z)); ED;
        } else if(op=='M') {
            x=rd()^las; y=rd()^las;
            update(x,y);
        } else if(op=='I') {
            x=rd()^las; y=rd()^las;
            insert(x,y); 
        }
    }

    return 0;
}

• 整体二分

#include <bits/stdc++.h>

#define N (int)(5e5+5)
#define ED puts("")

using namespace std;

struct node {
    int typ,l,r,val,id;
}q[N],q1[N],q2[N];

int sum[N];
int n,m,tot,cnt,ans[N],lsh[N],pre[N],lcnt;

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

void pr(int x) {
    if(x<0) {putchar('-');x=-x;}
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}

int lowbit(int x) {
    return x&(-x);
}

void add(int x,int y) {
    while(x<=n) sum[x]+=y,x+=lowbit(x);
}

int qry(int x) {
    int res=0;
    while(x) res+=sum[x],x-=lowbit(x);
    return res;
}

void solve(int l,int r,int L,int R) {
    if(l>r||L>R) return;
    int cnt1=0,cnt2=0,mid=(l+r)>>1;
    if(l==r) {
        for(int i=L;i<=R;i++) if(q[i].typ==2) ans[q[i].id]=lsh[l];
        return;
    }
    for(int i=L;i<=R;i++) {
        if(q[i].typ==2) {
            int qwq=qry(q[i].r)-qry(q[i].l-1);
            if(q[i].val<=qwq) q1[++cnt1]=q[i];
            else q[i].val-=qwq,q2[++cnt2]=q[i];
        } else {
            if(q[i].val<=mid) add(q[i].l,q[i].r),q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }
    }
    for(int i=1;i<=cnt1;i++) if(q1[i].typ==1) add(q1[i].l,-q1[i].r);
    for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[cnt1+L+i-1]=q2[i];
    solve(l,mid,L,L+cnt1-1); solve(mid+1,r,L+cnt1,R);
}

int main() {
    n=rd(); m=rd();
    char op[2]; int l,r,x;
    for(int i=1;i<=n;i++) {
        x=rd();
        q[++tot]=node{1,i,1,x,0};
        lsh[++lcnt]=x; pre[i]=x;
    }   
    for(int i=1;i<=m;i++) {
        cin>>op; l=rd(); r=rd();
        if(op[0]=='Q') {
            x=rd();
            q[++tot]=node{2,l,r,x,++cnt};
        } else {
            q[++tot]=node{1,l,-1,pre[l],0};
            q[++tot]=node{1,l,1,r,0};
            lsh[++lcnt]=r; pre[l]=r;
        }
    }
    sort(lsh+1,lsh+1+lcnt); lcnt=unique(lsh+1,lsh+1+lcnt)-lsh;
    for(int i=1;i<=tot;i++) {
        if(q[i].typ==1) q[i].val=lower_bound(lsh+1,lsh+1+lcnt,q[i].val)-lsh;
    }
    solve(1,lcnt,1,tot);
    for(int i=1;i<=cnt;i++) pr(ans[i]),ED;
    return 0; 
}

• 树状数组套主席树

#include <bits/stdc++.h>

#define N (int)(1e5+5)

using namespace std;

int rt[N],cx[20],cy[20],a[N];
int n,m,tot,totx,toty;

struct BIT {
    int ls[N*500],rs[N*500],sum[N*500];
    void update(int &cur,int l,int r,int x,int val) {
        if(!cur) cur=++tot;
        sum[cur]+=val;
        if(l==r) return;
        int mid=(l+r)>>1;
        if(x<=mid) update(ls[cur],l,mid,x,val);
        else update(rs[cur],mid+1,r,x,val);
    }
    int query(int l,int r,int k) {
        if(l==r) return l;
        int mid=(l+r)>>1,res=0;
        for(int i=1;i<=totx;i++) res+=sum[ls[cx[i]]];
        for(int i=1;i<=toty;i++) res-=sum[ls[cy[i]]];
        if(k<=res) {
            for(int i=1;i<=totx;i++) cx[i]=ls[cx[i]];
            for(int i=1;i<=toty;i++) cy[i]=ls[cy[i]];
            return query(l,mid,k);
        } else {
            for(int i=1;i<=totx;i++) cx[i]=rs[cx[i]];
            for(int i=1;i<=toty;i++) cy[i]=rs[cy[i]];
            return query(mid+1,r,k-res);
        }
    }
}T;

int lowbit(int x) {
    return x&(-x);
}

void modify(int pos,int x,int val) {
    for(;pos<=n;pos+=lowbit(pos)) T.update(rt[pos],0,1e9,x,val);
}

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

int main() {
    n=rd(); m=rd();
    for(int i=1;i<=n;i++) a[i]=rd(),modify(i,a[i],1);
    char op; int l,r,x;
    while(m--) {
        cin>>op; l=rd(); r=rd();
        if(op=='Q') {
            x=rd();
            totx=toty=0;
            for(int i=r;i;i-=lowbit(i)) cx[++totx]=rt[i];
            for(int i=l-1;i;i-=lowbit(i)) cy[++toty]=rt[i];
            printf("%d\n",T.query(0,1e9,x));
        } else {
            modify(l,a[l],-1); modify(l,a[l]=r,1);
        }
    }
}

• 矩阵第 k 大

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

#define M 505
#define N (int)(3e5+5)

using namespace std;

struct node {
    int x,y,val;
}a[N];

struct ques {
    int x,y,xx,yy,k,id;
}q[N];

int sum[M][M];
int n,m,ans[N];

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

bool cmp(node x,node y) {
    return x.val<y.val;
}

int lowbit(int x) {
    return x&(-x);
}

void add(int x,int y,int val) {
    int ny;
    while(x<=n) {
        ny=y;
        while(ny<=n) {
            sum[x][ny]+=val;
            ny+=lowbit(ny);
        }
        x+=lowbit(x);
    }
}

int qry(int x,int y) {
    int res=0,ny;
    if(!x||!y) return 0;
    while(x) {
        ny=y;
        while(ny) {
            res+=sum[x][ny];
            ny-=lowbit(ny);
        }
        x-=lowbit(x);
    }
    return res;
}

int query(int x,int y,int xx,int yy) {
    return qry(xx,yy)+qry(x-1,y-1)-qry(x-1,yy)-qry(xx,y-1);
}

ques t1[N],t2[N];
void solve(int L,int R,int l,int r) {
    if(L==R) {
        for(int i=l;i<=r;i++) {
            //cout<<q[i].k<<":";
            ans[q[i].id]=a[L].val;
        }
        return;
    }
    int mid=(L+R)>>1,cnt1=0,cnt2=0;
    for(int i=L;i<=mid;i++) add(a[i].x,a[i].y,1);
    for(int i=l;i<=r;i++) {
        int res=query(q[i].x,q[i].y,q[i].xx,q[i].yy);
        if(res>=q[i].k) t1[++cnt1]=q[i];
        else q[i].k-=res,t2[++cnt2]=q[i];
    //  cout<<":xgf "<<res<<" "<<i<<" "<<q[i].k<<" "<<L<<' '<<R<<endl;
    }
    for(int i=L;i<=mid;i++) add(a[i].x,a[i].y,-1);
    for(int i=1;i<=cnt1;i++) q[i+l-1]=t1[i];
    for(int i=1;i<=cnt2;i++) q[i+cnt1+l-1]=t2[i];
    solve(L,mid,l,l+cnt1-1); solve(mid+1,R,l+cnt1,r);
}

int main() {
    n=rd(); m=rd();
    int tot=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            a[++tot]=node{i,j,rd()};
    sort(a+1,a+1+tot,cmp);
    for(int i=1;i<=m;i++) {
        q[i]=ques{rd(),rd(),rd(),rd(),rd(),i};
    }
    solve(1,tot,1,m);
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
} 

• 树上路径第 k 大

#include <bits/stdc++.h>

#define N (int)(3e5+5)
#define ls (cur<<1)
#define rs (ls|1)

using namespace std;

struct node {
    int x,y,val,id;
}a[N<<1];

struct edge {
    int nex,to;
}e[N<<1];

bool vis[N];
int head[N],cnt,tot,fa[N],top[N],dep[N],son[N],id[N],sz[N];
int n,m,pre[N],lsh[N],ans[N],l_cnt;

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

void add(int x,int y) {
    e[++cnt]=edge{head[x],y};
    head[x]=cnt;
}

void dfs1(int x,int faa) {
    dep[x]=dep[faa]+1; fa[x]=faa; sz[x]=1;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        if(y==faa) continue;
        dfs1(y,x); sz[x]+=sz[y];
        if(sz[y]>sz[son[x]]) son[x]=y;
    }
}

void dfs2(int x,int tp) {
    top[x]=tp; id[x]=++tot;
    if(son[x]) dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}

int sum[N<<2];
void add(int cur,int l,int r,int x,int val) {
    if(l==r) {
        sum[cur]+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) add(ls,l,mid,x,val);
    else add(rs,mid+1,r,x,val);
    sum[cur]=sum[ls]+sum[rs];
}

int query(int cur,int l,int r,int cl,int cr) {
    if(cl>cr) return 0;
    if(cl<=l&&r<=cr) return sum[cur];
    int mid=(l+r)>>1,res=0;
    if(cl<=mid) res=query(ls,l,mid,cl,cr);
    if(cr>mid) res+=query(rs,mid+1,r,cl,cr);
    return res;
}

int qry(int x,int y) {
    int res=0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);//cout<<x<<" "<<y<<endl;
        res+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    return res+query(1,1,n,id[x],id[y]);
}

node q1[N],q2[N];
void solve(int L,int R,int l,int r) {
    if(l>r) return;
    if(L==R) {
        for(int i=l;i<=r;i++) {
            if(a[i].id==-1) continue;
            ans[a[i].id]=lsh[L];
        //  cout<<lsh[L]<<" "<<a[i].val<<endl;
        }
        //cout<<L<<" "<<l<<" "<<r<<endl;
        return;
    }
    int mid=(L+R)>>1,cnt1=0,cnt2=0;
    for(int i=l;i<=r;i++) {
        if(a[i].id==-1) {
            if(a[i].val<=mid) q1[++cnt1]=a[i];
            else q2[++cnt2]=a[i],add(1,1,n,id[a[i].x],a[i].y);
        } else {
            int res=qry(a[i].x,a[i].y);
            if(res>=a[i].val) q2[++cnt2]=a[i];
            else a[i].val-=res,q1[++cnt1]=a[i];
        }
    }
    for(int i=1;i<=cnt2;i++) if(q2[i].id==-1) add(1,1,n,id[q2[i].x],-q2[i].y);
    for(int i=1;i<=cnt1;i++) a[i+l-1]=q1[i];
    for(int i=1;i<=cnt2;i++) a[i+l+cnt1-1]=q2[i];
    solve(L,mid,l,l+cnt1-1); solve(mid+1,R,l+cnt1,r);
}

int main() {
    n=rd(); m=rd();
    int tot1=0,x,y;
    for(int i=1;i<=n;i++) pre[i]=rd(),a[++tot1]=node{i,1,pre[i],-1},lsh[++l_cnt]=pre[i];
    for(int i=1;i<n;i++) x=rd(),y=rd(),add(x,y),add(y,x);
    dfs1(1,0); dfs2(1,1);   
    for(int i=1;i<=m;i++) {
        x=rd();
        if(x==0) {
            x=rd(); y=rd();
            a[++tot1]=node{x,-1,pre[x],-1};
            a[++tot1]=node{x,1,y,-1};
            lsh[++l_cnt]=pre[x]=y;
        } else {
            a[++tot1]=node{rd(),rd(),x,i};
            vis[i]=1;
        }
    }
    sort(lsh+1,lsh+1+l_cnt);// l_cnt=unique(lsh+1,lsh+1+l_cnt)-lsh-1;
    for(int i=1;i<=tot1;i++) {
        if(a[i].id==-1) a[i].val=lower_bound(lsh+1,lsh+1+l_cnt,a[i].val)-lsh;
    } 
    solve(0,l_cnt,1,tot1);
    for(int i=1;i<=m;i++) {
        if(vis[i]) ans[i]?printf("%d\n",ans[i]):puts("invalid request!");
    }
    return 0;
}

• 莫队区间第 k 大

#include <bits/stdc++.h>

#define N (int)(2e5+5)

using namespace std;

struct ques {
    int l,r,k,id;
}q[N];

int n,m,bl,pos[N],ans[N],a[N],lsh[N],sum[N];

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

bool cmp(ques x,ques y) {
    return pos[x.l]==pos[y.l]?pos[x.l]&1?x.r<y.r:x.r>y.r:x.l<y.l;
}

int lowbit(int x) {
    return x&(-x);
}

void add(int x,int w) {
    if(!x) return; 
    while(x<N) {
        sum[x]+=w,x+=lowbit(x);
        //cout<<x<<endl;
    }
}

int qry(int x) {
    int res=0;
    while(x) res+=sum[x],x-=lowbit(x);
    return res;
}

int solve(int k) {
    int l=1,r=n,res=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(qry(mid)>=k) res=mid,r=mid-1;
        else l=mid+1;
    }
    return lsh[res];
}

int main() {
    n=rd(); m=rd(); bl=sqrt(n);
    for(int i=1;i<=n;i++) pos[i]=(i-1)/bl+1,lsh[i]=a[i]=rd();
    sort(lsh+1,lsh+1+n);
    for(int i=1;i<=n;i++) a[i]=lower_bound(lsh+1,lsh+1+n,a[i])-lsh;
    //for(int i=1;i<=n;i++) cout<<a[i]<<" "; puts("");
    for(int i=1;i<=m;i++) {
        q[i]=ques{rd(),rd(),rd(),i};
    }
    sort(q+1,q+1+m,cmp);
    int l=0,r=0,cl,cr;
    for(int i=1;i<=m;i++) {
        cl=q[i].l; cr=q[i].r;
    //  cout<<cl<<" "<<cr<<endl;
        while(l<cl) add(a[l++],-1);
        while(l>cl) add(a[--l],1);
        while(r<cr) add(a[++r],1);
        while(r>cr) add(a[r--],-1);
        ans[q[i].id]=solve(q[i].k);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

参考资料：

https://www.cnblogs.com/fusiwei/p/11432323.html

https://oi-wiki.org/basic/quick-sort/

https://www.luogu.com.cn/blog/2-6-5-3-5/zheng-ti-er-fen-xie-jue-jing-tai-ou-jian-di-k-xiao-di-you-hua