#include <iostream>
using namespace std;

const int MAX_VAL = 100; // 值域0~100
int tree[4 * (MAX_VAL + 1)]; // 静态数组，存储每个节点对应区间内数值的总出现次数

// 插入一个值x（出现次数+1）
// p: 当前节点编号, l,r: 当前节点覆盖的值域区间
void insert(int p, int l, int r, int x) {
    if (l == r) {
        tree[p]++; // 叶子节点，次数加1
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        insert(p * 2, l, mid, x); // 左子树
    } else {
        insert(p * 2 + 1, mid + 1, r, x); // 右子树
    }
    tree[p] = tree[p * 2] + tree[p * 2 + 1]; // 更新当前节点
}

// 查询第k小的数（k从1开始计数）
// 返回该数值
int query_kth(int p, int l, int r, int k) {
    if (l == r) {
        return l; // 叶子节点就是答案
    }
    int mid = (l + r) / 2;
    if (tree[p * 2] >= k) {
        return query_kth(p * 2, l, mid, k); // 第k小在左子树
    } else {
        return query_kth(p * 2 + 1, mid + 1, r, k - tree[p * 2]); // 右边，减去左边个数
    }
}

int main() {
    int arr[] = {5,3,7,3,9,5,2}; // 待插入数据（成绩）
    int n = sizeof(arr) / sizeof(arr[0]);

    // 依次插入所有成绩
    for (int i = 0; i < n; i++) {
        insert(1, 0, MAX_VAL, arr[i]);
    }

    // 查询第1小、第2小、第4小的数
    cout << "第1小的数: " << query_kth(1, 0, MAX_VAL, 1) << endl; // 2
    cout << "第2小的数: " << query_kth(1, 0, MAX_VAL, 2) << endl; // 3
    cout << "第4小的数: " << query_kth(1, 0, MAX_VAL, 4) << endl; // 5
    return 0;
}

第1小的数: 2
第2小的数: 3
第4小的数: 5

class WeightSegmentTree:
    def __init__(self, max_val):
        self.max_val = max_val
        # 树数组，大小4*(max_val+1) 足够
        self.tree = [0] * (4 * (max_val + 1))

    def insert(self, p, l, r, x):
        """插入数值x（出现次数加1）"""
        if l == r:
            self.tree[p] += 1  # 叶子节点，次数加1
            return
        mid = (l + r) // 2
        if x <= mid:
            self.insert(p * 2, l, mid, x)  # 左子树
        else:
            self.insert(p * 2 + 1, mid + 1, r, x)  # 右子树
        self.tree[p] = self.tree[p * 2] + self.tree[p * 2 + 1]  # 更新父节点

    def query_kth(self, p, l, r, k):
        """查询第k小的数（k从1开始）"""
        if l == r:
            return l
        mid = (l + r) // 2
        left_cnt = self.tree[p * 2]  # 左子树的总出现次数
        if left_cnt >= k:
            return self.query_kth(p * 2, l, mid, k)
        else:
            return self.query_kth(p * 2 + 1, mid + 1, r, k - left_cnt)

if __name__ == "__main__":
    arr = [5, 3, 7, 3, 9, 5, 2]
    max_val = 100  # 成绩范围0~100
    st = WeightSegmentTree(max_val)
    for x in arr:
        st.insert(1, 0, max_val, x)

    print("第1小的数:", st.query_kth(1, 0, max_val, 1))  # 2
    print("第2小的数:", st.query_kth(1, 0, max_val, 2))  # 3
    print("第4小的数:", st.query_kth(1, 0, max_val, 4))  # 5

#include <iostream>
using namespace std;

struct Node {
    int lc, rc; // 左右孩子下标，0表示不存在
    int cnt;    // 当前节点区间内数值的总出现次数
} node[1000000]; // 预留足够大，一般n * 30
int root = 1, tot = 1; // root: 根节点编号, tot: 当前已用节点数

// 插入数值x（出现次数+1），p为当前节点引用，用于可能创建新节点
void insert(int &p, int l, int r, int x) {
    if (p == 0) {
        p = ++tot; // 动态创建新节点，分配编号
        node[p].lc = node[p].rc = 0; // 初始化孩子为空
        node[p].cnt = 0;
    }
    if (l == r) {
        node[p].cnt++; // 叶子节点，次数加1
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        insert(node[p].lc, l, mid, x); // 递归左子树
    } else {
        insert(node[p].rc, mid + 1, r, x); // 递归右子树
    }
    // 更新当前节点：左右子树的cnt之和，注意孩子可能不存在
    node[p].cnt = (node[node[p].lc].cnt) + (node[node[p].rc].cnt);
}

// 查询第k小的数（k从1开始）
int query_kth(int p, int l, int r, int k) {
    if (l == r) {
        return l; // 叶子节点即为答案
    }
    int mid = (l + r) / 2;
    int left_cnt = node[node[p].lc].cnt; // 左子树的出现次数，若左孩子不存在则为0
    if (left_cnt >= k) {
        return query_kth(node[p].lc, l, mid, k);
    } else {
        return query_kth(node[p].rc, mid + 1, r, k - left_cnt);
    }
}

int main() {
    int arr[] = {100, 3, 1000, 5, 7, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 插入所有数值，值域设为 0 ~ 1e9
    for (int i = 0; i < n; i++) {
        insert(root, 0, 1000000000, arr[i]);
    }

    cout << "第1小的数: " << query_kth(root, 0, 1000000000, 1) << endl; // 3
    cout << "第2小的数: " << query_kth(root, 0, 1000000000, 2) << endl; // 3
    cout << "第3小的数: " << query_kth(root, 0, 1000000000, 3) << endl; // 5
    return 0;
}

第1小的数: 3
第2小的数: 3
第3小的数: 5

class Node:
    __slots__ = ('lc', 'rc', 'cnt')  # 节省内存
    def __init__(self):
        self.lc = None  # 左孩子（Node对象或None）
        self.rc = None  # 右孩子
        self.cnt = 0    # 出现次数

class DynamicWeightSegmentTree:
    def __init__(self, left, right):
        self.root = Node()  # 根节点
        self.L = left       # 值域左边界
        self.R = right      # 值域右边界

    # 内部插入函数，返回更新后的节点
    def _insert(self, p, l, r, x):
        if p is None:
            p = Node()  # 动态创建新节点
        if l == r:
            p.cnt += 1
            return p
        mid = (l + r) // 2
        if x <= mid:
            p.lc = self._insert(p.lc, l, mid, x)
        else:
            p.rc = self._insert(p.rc, mid + 1, r, x)
        # 更新当前节点次数（注意处理None）
        left_cnt = p.lc.cnt if p.lc else 0
        right_cnt = p.rc.cnt if p.rc else 0
        p.cnt = left_cnt + right_cnt
        return p

    # 对外插入接口
    def insert_value(self, x):
        self.root = self._insert(self.root, self.L, self.R, x)

    # 内部查询第k小函数
    def _query_kth(self, p, l, r, k):
        if l == r:
            return l
        mid = (l + r) // 2
        left_cnt = p.lc.cnt if p.lc else 0
        if left_cnt >= k:
            return self._query_kth(p.lc, l, mid, k)
        else:
            return self._query_kth(p.rc, mid + 1, r, k - left_cnt)

    # 对外查询接口
    def kth(self, k):
        return self._query_kth(self.root, self.L, self.R, k)

if __name__ == "__main__":
    arr = [100, 3, 1000, 5, 7, 3]
    st = DynamicWeightSegmentTree(0, 1000000000)  # 值域0~10^9
    for x in arr:
        st.insert_value(x)

    print("第1小的数:", st.kth(1))  # 3
    print("第2小的数:", st.kth(2))  # 3
    print("第3小的数:", st.kth(3))  # 5