Problem

传送门

一个长度为n的序列，支持一堆操作，大致操作如下：

1.k在区间的排名(由小到大)2.区间第k小；3.单点修改；4&5：k的在区间上的前驱/后继。

Solution

右边大佬说树套树很简单，就是两个基本操作套起来即可。

然后我码了一个半小时才码完。

虽然话没说错，树状数组套主席树……

但是这代码……

算了，还是太菜了……

2,3操作：

其实做法比较好理解，树状数组具有前缀性，主席树也是利用前缀

所以可以将树状数组的每一个节点上建一颗主席树

这样就可以完美的实现修改操作了

具体实现……就是把原本的树状数组一般操作改为主席树上的修改操作

询问的时候将树状数组上\(lowbit\)到的点全部带进去主席树里去询问就可以了。

以上是第2,3操作(搞了半天才完成2,3操作)

1操作：

考虑线段树的遍历过程

如果当前权值线段树的\(mid\)大于当前询问的权值k，那么我们会走向左儿子，否则往走向右儿子

而且，当我们走向右儿子时k一定大于左边的所有数

所以我们只要在此时加左子树的数的个数即可

4,5操作：

既然知道了任意数在区间里的\(rank\)前驱和后继就很好处理了

\(k\)前驱只需要查\(k\)在区间里的\(rank\)，区间排名为\(rank - 1\)的数即为所求

\(k\)的后继则需要知道\(k\)在区间中的\(rank\)与\(k\)在区间中出现的次数\(num\)，再求区间中排名为\(rank+num\)的数即可。

放一份奇丑的代码，以后再改。

Code

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
    int res = 0, fl = 1;
    char r = getchar();
    for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
    for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
    return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 4e5 + 10;

struct CMtree{
    int ls, rs, sum;
}tre[Maxn << 7];
struct SGT{
    int ch[20],siz;
    SGT(){ siz = 0;}
    SGT Ls(){
        SGT B;
        for (int i = 1; i <= siz; ++i) B.ch[i] = tre[ch[i]].ls;
        B.siz = siz;
        return B;
    }
    SGT Rs(){
        SGT B;
        for (int i = 1; i <= siz; ++i) B.ch[i] = tre[ch[i]].rs;
        B.siz = siz;
        return B;
    }
    int sum(){
        int num = 0;
        for (int i = 1; i <= siz; ++i) num += tre[ch[i]].sum;
        return num;
    }
};
int A[Maxn], n, m, cnt, root[Maxn << 6];
int INF = 1e8 + 10;
pii operator + (const pii a, const pii b){
    return mp(a.fst + b.fst, a.snd + b.snd);
}
namespace CMT{
    inline void modify(int &rt,int l, int r, int pos, int v){
        if(!rt) rt = ++cnt;
        tre[rt].sum += v;
        if(l == r) return;
        int mid = l + r >> 1;
        if(mid >= pos) modify(tre[rt].ls, l, mid, pos, v);
        else modify(tre[rt].rs, mid + 1, r, pos, v);
    }
    inline void build(int &rt, int grt,int l, int r, int pos){
        tre[rt = ++cnt] = tre[grt];
        tre[rt].sum++;
        if(l == r) return;
        int mid = l + r >> 1;
        if(mid >= pos) build(tre[rt].ls, tre[grt].ls, l, mid, pos);
        else build(tre[rt].rs, tre[grt].rs, mid + 1, r, pos);
    }
    inline int Query(SGT a, SGT b, int l, int r, int k){
        if(l == r) return l;
        int mid = l + r >> 1, t = b.Ls().sum() - a.Ls().sum();
        //printf("%d %d %d %d\n", l, r, t, k);
        if(k <= t) return Query(a.Ls(), b.Ls(), l, mid, k);
        else return Query(a.Rs(), b.Rs(), mid + 1, r, k - t);
    }
    inline pii rank(SGT a, SGT b,int l,int r, int k){
        if(l == r) {
            return mp(1,b.sum() - a.sum());
        }
        int mid = l + r >> 1;
        if(k <= mid) return rank(a.Ls(), b.Ls(), l, mid, k);
        else return mp(b.Ls().sum() - a.Ls().sum(), 0) + rank(a.Rs(), b.Rs(), mid + 1, r, k);
    }
}
namespace BIT{
    int lst[Maxn];
    inline int lowbit(int x) {return x & -x;}
    inline void change(int pos,int a, int b){
        for (; pos <= n; pos += lowbit(pos))
            CMT :: modify(root[pos], 1,INF, a, -1), CMT :: modify(root[pos], 1,INF, b, 1);
    }
    inline void add(int pos,int a){
        for (; pos <= n; pos += lowbit(pos)){
            CMT :: build(root[pos], lst[pos], 1, INF, a), lst[pos] = root[pos];
        }
    }
    inline pii Query(int l, int r, int k, bool fl){
        SGT a, b;
        for (int i = l - 1; i > 0; i -= lowbit(i)) a.ch[++a.siz] = root[i];
        for (int i = r; i > 0; i -= lowbit(i)) b.ch[++b.siz] = root[i];
        if(fl) return mp(CMT :: Query(a, b, 1, INF, k), 0);
        else return CMT :: rank(a, b, 1, INF, k);
    }
}
void Front(int l, int r, int k) {
    pii Rank = BIT::Query(l, r, k, 0);
    if(Rank.fst == 1) printf("-2147483647\n");
    else printf("%d\n",BIT::Query(l, r, Rank.fst - 1, 1).fst);
}
void Next(int l, int r, int k){
    pii Rank = BIT::Query(l, r, k, 0);
    int all = r - l + 1;
    if(Rank.fst + Rank.snd > all) printf("2147483647\n");
    else printf("%d\n",BIT::Query(l, r, Rank.fst + Rank.snd, 1).fst);
}
int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) A[i] = read(), BIT::add(i, A[i]);
    while(m--){
        int opt = read();
        if(opt == 3) {int pos = read(), k = read(); BIT::change(pos,A[pos],k); A[pos] = k; continue;}
        int l = read(), r = read(), k = read();
        if(opt == 1) printf("%d\n",BIT::Query(l, r, k, 0).fst);
        if(opt == 2) printf("%d\n",BIT::Query(l, r, k, 1).fst);
        if(opt == 4) Front(l, r, k);
        if(opt == 5) Next(l, r, k);
    }
    return 0;
}