传送门

我永远喜欢离线分治算法

题意不多说，带修改的区间第k大。

整体二分。

整体二分也叫基于值域的分治算法。

二分答案，先将整个序列的值域二分得mid。对于整个操作序列1~M，可以依次知道在操作区间Mi ：[ l , r ] <= mid 的值有多少个。具体来说就是利用一个树状数组，如果A[ i ] <= mid 那么树状数组add( i , 1)。 如果带有修改操作，那么就把修改拆成在位置 i 加一个数和减一个数。

如果对于第k大查询Mi，有cnt个数在区间内小于k，很明显如果cnt >= k的话答案就在左值域里面。否则就在右值域里面。(注意，二分值域的意义就是二分查询的答案)

然后，对于这些询问进行分类。在左值域的询问和操作分一堆，在右值域的询问和操作分一堆。这是个分治的过程，继续往下递归这两类询问。直到值域二分的边界，所剩下的询问的答案就是这个值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
struct rec{
    int t, x, y, z;
}a[maxn], lb[maxn], rb[maxn];
unordered_map<int,int> ump, rg;
set<int> st;
int n, m;
int seq[maxn];
int c[maxn], tot;
void add(int x, int v)
{
    for(; x <= n; x += x & -x) c[x] += v; 
}
int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
int ans[maxn];
void solve(int lv, int rv, int st, int ed)
{
    if(st > ed) return ;
    if(lv == rv)
    {
        for(int i = st; i <= ed; i++) ans[a[i].t] = lv;
        return ;
    }
    int mid = (lv + rv) >> 1;
    int lt = 0, rt = 0;
    for(int i = st; i <= ed; i++)
    {
        if(a[i].t == -1)
        {
            if(ump[a[i].z] <= mid) add(a[i].x, -1), lb[++lt] = a[i];
            else rb[++rt] = a[i];
        }
        else if(a[i].t == 0)
        {
            if(ump[a[i].z] <= mid) add(a[i].x, 1), lb[++lt] = a[i];
            else rb[++rt] = a[i];
        }
        else 
        {
            int cnt = ask(a[i].y) - ask(a[i].x - 1);
            if(cnt >= a[i].z) lb[++lt] = a[i];
            else a[i].z -= cnt, rb[++rt] = a[i];
        }
    }
    for(int i = 1; i <= lt; i++) a[st + i - 1] = lb[i];
    for(int i = 1; i <= rt; i++) a[st + lt + i - 1] = rb[i];
    for(int i = st; i <= ed; i++) 
        if(a[i].t == 0 && ump[a[i].z] <= mid) add(a[i].x, -1); 
        else if(a[i].t == -1 && ump[a[i].z] <= mid) add(a[i].x, 1);
    solve(lv, mid, st, lt + st - 1);
    solve(mid + 1, rv, lt + st, ed); 
}
int main()
{
    int T; cin >> T;
    while(T--)
    {
        int t = 0;
        st.clear();
        ump.clear();
        rg.clear();
        memset(c, 0, sizeof c);
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &seq[i]);
            a[++t] = {0, i, i, seq[i]};
            st.insert(seq[i]);
        }
        char op[5];
        int qt = 0;
        for(int i = 1; i <= m; i++)
        {
            scanf("%s", op);
            if(*op == 'Q')
            {
                int l, r, k;
                scanf("%d%d%d", &l, &r, &k);
                a[++t] = {++qt, l, r, k};
                //st.insert(k);
            }
            else 
            {
                int l, k;
                scanf("%d%d", &l, &k);
                a[++t] = {-1, l, l, seq[l]};
                a[++t] = {0, l, l, k};
                seq[l] = k;
                st.insert(k);
            }
        }
        tot = 0;
        for(auto it = st.begin(); it != st.end(); it++) ump[*it] = ++tot, rg[tot] = *it;
        //for(int i = 1; i <= t; i++) cout << a[i].x << " "; puts(""); 
        solve(1, tot, 1, t);
        for(int i = 1; i<= qt; i++) printf("%d\n", rg[ans[i]]);
    }
}

注意树状数组要进行还原

写代码的时候注意先判断值域再操作，如果不符合就不用继续操作树状数组了。