Hellc

本文主要讨论以 主席树 这种数据结构解决 静态区间排名 的问题。

问题

给定一个序列，每次询问某个区间 $[l, r)$ 中，排名为 $k$ 的元素为多少。

考虑削弱版本

假如每次询问不是指定区间，而是询问 整个序列 上排名为 $k$ 的元素，那么问题还是比较简单，可以使用 权值线段树 解决。

权值线段树？

权值线段树与传统的区间线段树是不同的。

一个权值线段树上的节点，依然代表一段区间，不过代表的是值域中的一段区间，维护了 值 在此范围内的所有元素的信息。

而传统的区间线段树代表的是位置中的一段区间，维护的是 位置 在此区间内的所有元素的信息。

对于本题而言，在权值线段树上，我们可以维护每个区间内元素出现的次数，查询的时候，类似平衡树，根据左子树次数和目标排名的大小关系，决定向左走还是向右走，复杂度 $O(\log n)$。

一般的，权值线段树的区间是对 值域 开的，有时值域会过大，在时间上和空间上都难以承受，此时有两种解决方案：

• 对序列进行 离散化，将值域映射到 $ O(n) $ 级别。
• 线段树 动态开节点，只有修改或查询涉及到的节点才真正的创建出来。

如何支持某个区间上的操作？

我们想，假如对于每个询问区间，我们能够拥有对应的权值线段树，即只把这个区间中的元素插入进去，所得到的树，那样的话就好了。

~~我们可以对所有的区间分别建立线段树，然后查询就好啦！~~

显然上面是胡扯，因为区间数量是 $O(n^2)$ 的。

我们考虑前缀和的思想，对每个前缀序列建立权值线段树，然后通过 前缀线段树 相减即可得到任意区间。

具体来说，令 $T_i$ 表示将序列上前 $i$ 个元素插入所形成的权值线段树（即对应区间 $[0, i)$），那么假如我们询问区间 $[l, r)$，只需要用 $T_r$ 减去 $T_l$ 即可。

要注意这些线段树的形态是完全相同的，因为都是对值域建立，所谓线段树的相减，其实是指的对应节点上的信息相减，这便需要维护的信息满足 区间减法 ，这也就是使用主席树的一个重要条件。

这个问题就这样解决了吗？ 不，还有一个问题需要考虑，那就是空间问题，以上算法的空间复杂度是 $O(n^2\log n)$的，这难以承受！

我们可以使用 可持久化/函数式 思想解决这个问题。

可持久化？ 函数式？

我们注意到，在上述算法的前缀线段树中，任意相邻两棵树，仅有一个元素的差异，而一个元素在线段树上只会影响数量为 $O(\log n)$ 的节点，这是从根出发的一条链，而其他的部分，与上一颗完全相同，既然完全相同，为什么要复制一份呢？直接拿来用不就可以了吗！

也就是说，每次插入一个元素，我们仅新建一条规模为 $O(\log n)$ 的链，而其他部分，直接指向上一课线段树的相应节点。

这便是 可持久化/函数式 的思想，每次所谓修改操作不改动原数据结构，而是（只）新建所有变化的部分，相当于使之支持历史版本的查询，并通过它们之间的共有数据来降低空间与时间消耗。

至此，问题通过主席树完美解决，总的时间和空间复杂度都为 $O(n\log n)$。

关于本问题的带修改版本

如果要求支持修改某一位上的数，那么主席树就无法胜任了。

参阅 带修改的区间排名 - 学习笔记

例题

POJ 2104 k-th Number

模板题。

动态分配内存会 T，需要静态分配，可以写内存池。

讲讲做这题的经历，学了主席树，信心满满的写好这题，交上去，TLE，想到是值域过大的问题，于是离散化一发，交上去，TLE，于是又写了动态开点，交上去，TLE，不久想到是动态分配内存的问题，于是写好内存池，交上去，还是 TLE，怀疑读入问题，写了一发读入优化，依旧 TLE，怀疑是编译器的锅，于是从 G++ 改到 C++，TLE。

然后开始怀疑人生...

最后历尽艰辛，问题终于找到，线段树的静态节点我只开到了 $O(n)$，然而此题的空间复杂度是 $O(n\log n)$ 的...

（我写内存池时，预分配空间不够是还是动态开，所以会 TLE 而不会 RE）

真想给自己一刀...

以下是~~（加了各种奇怪东西的）~~代码，只看SegmentTree和PresentTree这两个结构体的代码就好啦：

#include <cstdio>
#include <algorithm>

namespace IO{
    const int IN_SIZE = 1 << 15, OUT_SIZE = 1 << 15;
    char inBuf[IN_SIZE], outBuf[OUT_SIZE];
    char *S, *T, ch;
    int now;

    inline void init(){
        S = T = inBuf;
        now = 0;
    }

    inline char getchar(){
        if(S == T) S = inBuf, T = inBuf + fread(inBuf, 1, IN_SIZE, stdin);
        if(S == T) return EOF;
        return *S++;
    }

    template <typename Int> inline void readint(Int &x){
        int f = 1;
        for(ch = getchar(); ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1;
        for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ '0');
        x *= f;
    }

    inline void putAll(){
        if(now) fwrite(outBuf, 1, now, stdout), now = 0;
    }

    inline void putchar(char ch){
        outBuf[now++] = ch;
        if(now == OUT_SIZE) putAll();
    }

    template <typename Int> inline void putint(Int x){
        if(x < 0) putchar('-'), putint(-x);
        else{
            if(x > 9) putint(x / 10);
            putchar(x % 10 + '0');
        }
    }

    inline void end(){
        putAll();
    }
}

const int MAXN = 100000;

struct SegmentTree{
    SegmentTree *lc, *rc;
    int l, r;
    int cnt;
    
    SegmentTree(int l = 0, int r = 0) : lc(NULL), rc(NULL), l(l), r(r), cnt(0) {}

    void pushDown();
    void update();
    void copyTo(SegmentTree *& v) const;
    SegmentTree *insert(int x) const;
};

template <typename T, size_t AMOUNT> struct MemoryPool{
    char preAlloc[AMOUNT * sizeof(T)];
    T *cur;
    T *recycle[AMOUNT], **recur;

    MemoryPool(){
        cur = (T*)preAlloc;
        recur = recycle;
    }

    T* operator()(){
        if(recur != recycle) return *recur--;
        else if(cur != (T*)preAlloc + AMOUNT) return cur++;
        else return (T*) (new char[sizeof(T)]);
    }

    void free(T *v){
        if(recur != recycle + AMOUNT) *recur++ = v;
    }
};

MemoryPool<SegmentTree, MAXN * 20> alloc;

inline void SegmentTree::pushDown(){
    if(!lc){
        lc = new (alloc()) SegmentTree(l, l + r >> 1);
        rc = new (alloc()) SegmentTree(l + r >> 1, r);
    }    
}

inline void SegmentTree::update(){
    cnt = lc->cnt + rc->cnt;
}

inline void SegmentTree::copyTo(SegmentTree *&v) const{
    *v = *this;
}

inline SegmentTree *SegmentTree::insert(int x) const{
    SegmentTree *v = new (alloc()) SegmentTree();
    this->copyTo(v);
    if(r - l != 1){
        v->pushDown();
        
        int mid = l + r >> 1;
        if(x < mid) v->lc = v->lc->insert(x); else v->rc = v->rc->insert(x);

        v->update();
    } else v->cnt++;
    return v;
}

struct PresentTree{
    SegmentTree *T[MAXN + 1]; // T[i] : a[0, i)
    
    void build(int a[], int n){
        T[0] = new SegmentTree(0, n);
        for(int i = 1; i <= n; i++) T[i] = T[i - 1]->insert(a[i - 1]);
    }
    
    int select(SegmentTree *a, SegmentTree *b, int k){
        if(a->r - a->l == 1) return a->l;
        
        a->pushDown(), b->pushDown();
        
        int cnt = b->lc->cnt - a->lc->cnt;
        int mid = a->l + a->r >> 1;
        
        if(k < cnt) return select(a->lc, b->lc, k);
        else return select(a->rc, b->rc, k - cnt);
    }
    
    int select(int l, int r, int k){
        return select(T[l], T[r], k);
    }
} solver;

int a[MAXN], n;
int origin[MAXN], size;

inline void disc(int a[], int n){
    std::copy(a, a + n, origin);
    std::sort(origin, origin + n);
    size = std::unique(origin, origin + n) - origin;
    for(int i = 0; i < n; i++){
        a[i] = std::lower_bound(origin, origin + size, a[i]) - origin;
    }
}

int main(){
    IO::init();
    
    int m;
    IO::readint(n), IO::readint(m);
    for(int i = 0; i < n; i++) IO::readint(a[i]);
    
    disc(a, n);
    solver.build(a, n);
    
    for(int i = 0; i < m; i++){
        int l, r, k;
        IO::readint(l), IO::readint(r), IO::readint(k);
        l--, r--, k--;
        IO::putint(origin[ solver.select(l, r + 1, k) ]), IO::putchar('\n');
    }

    IO::end();
    return 0;
}