HDU 2665 K-th Number

Description

给出一个序列，查询某段区间里第k小的数字

Analyze

跟区间有关的算法/数据结构有哪些？

尺取? 前缀和(与差分)? 莫队? 线段树? 树状数组? ……

而主席树，我认为是：以线段树为结构单元的前缀和序列

Study Blog

https://www.cnblogs.com/LonecharmRiver/articles/9087536.html

https://www.cnblogs.com/zyf0163/p/4749042.html

Code of HDU 2665 K-th Number

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define M 200010

int node_cnt, n, m;///节点标号、数组大小、查询个数
int sum[M << 5];///区间val
int rt[M];///根节点标号
int lc[M << 5], rc[M << 5];///当前结点左右子节点标号
int a[M], b[M];///原序列和离散序列
int p;///待修改点

///引用版初始化 amazing! Identical with the old way.
void build(int & now, int l, int r)///通过引用，为传入的变量赋值
{
    now = ++node_cnt;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(lc[now], l, mid);
    build(rc[now], mid + 1, r);
}

int Build(int l, int r)///非引用版初始化
{
    int now = ++node_cnt;
    if(l < r)
    {
        int mid = (l + r) >> 1;
        lc[now] = Build(l, mid);
        rc[now] = Build(mid + 1, r);
    }
    return now;
}

///单点修改
int modify(int now, int l, int r)///返回新的根节点标号
{
    int nxt = ++node_cnt;

    ///"指向" 原先的标号
    lc[nxt] = lc[now];
    rc[nxt] = rc[now];
    sum[nxt] = sum[now] + 1;
    if(l == r)///单点修改的终点
        return nxt;
    int mid = (l + r) >> 1;
    if(p <= mid)
        lc[nxt] = modify(lc[nxt], l, mid);
    else
        rc[nxt] = modify(rc[nxt], mid + 1, r);
    return nxt;
}

///u -> node of l - 1
///v -> node of r
int query(int u, int v, int l, int r, int k)///反回相应叶子节点标号
{
    int ans, mid = ((l + r) >> 1);
    int x = sum[lc[v]] - sum[lc[u]];///左孩子比右孩子更单纯
    if(l == r)
        return l;
    if(k <= x)
        ans = query(lc[u], lc[v], l, mid, k);
    else
        ans = query(rc[u], rc[v], mid + 1, r, k-x);
    return ans;
}

int main()
{
    int t, l, r, k, q, ans;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]), b[i] = a[i];
        sort(b + 1, b + n + 1);
        q = unique(b + 1, b + n + 1) - (b + 1);

        node_cnt = 0;
        build(rt[0], 1, q);
        for(int i = 1; i <= n; ++i)
        {
            p = lower_bound(b + 1, b + q + 1, a[i]) - b;
            rt[i] = modify(rt[i - 1], 1, q);
        }
        while(m--)
        {
            scanf("%d%d%d", &l, &r, &k);
            ans = query(rt[l - 1], rt[r], 1, q, k);
            printf("%d\n", b[ans]);
        }
    }
    return 0;
}

Something I want to say

主席树：以线段树为结构单元的前缀和序列

其体现的有关前缀和的特点：

以(前值)旧值更新(后值)新值

后值减(前值-1)代表中间区间的值

code中建树函数build用到了引用(也有非引用版)

引用：给变量一个新名字，喊着他的新名字让他去做事等效于喊他原来的名字让他去做事

为什么不能一直喊他原名字呢？当他处于不同的空间需要有不同的名字以区分

引用常常用在递归中，往往是深层递归中他得到一个值，使得前一层的他有了同样的值

主席树每棵节点保存的是一颗线段树，(时空两方面)维护的区间相同，结构相同，保存的信息不同，因此具有了加减性(前缀和性质)

别名：可持久化线段树

可持久化，后一刻可以参考前一刻的状态，二者共同部分很多

一颗线段树的节点维护的是当前节点对应区间的信息

倘若每次区间都不一样，就会给处理带来一些困难

有时可以直接细分区间然后合并，此种情况线段树可以直接搞定

但有时无法通过直接划分区间来求解，如频繁询问区间第k小元素

这时便需要用可持久化线段树