题解：K大数查询

一、题目分析

本题有(N)个位置和(M)个操作，每个位置可存储多个数。操作分为两种：一是在指定区间的每个位置加入一个数；二是查询指定区间内第(c)大的数。

二、解题思路

本题使用主席树（可持久化线段树）结合离散化来解决。主席树用于处理区间相关的统计信息，离散化用于减少数据范围，提高空间和时间效率。

（一）数据结构定义

struct Tree
{
    int l, r;
    LL sum, add;
}tr[P];
int L[M], R[M], T[M], idx;
struct Query
{
    int op, a, b, c;
}q[N];
vector<int> nums;

• Tree结构体表示线段树节点，包含区间左右端点l和r，节点统计值sum（用于记录满足条件的元素个数），以及懒标记add。
• L[M]、R[M]、T[M]分别存储线段树节点的区间信息和版本信息，idx用于节点编号。
• Query结构体存储每个操作的信息，包括操作类型op，以及操作涉及的位置和参数a、b、c。
• nums向量用于存储需要离散化处理的数值。

（二）辅助函数

1. 离散化函数get：

int get(int x)
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

返回数值x在离散化数组nums中的下标。

1. 建树函数build：

void build(int u, int l, int r)
{
    L[u] = l, R[u] = r, T[u] = ++ idx;
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

构建线段树，初始化节点的区间信息和版本号，递归构建左右子树。

1. 区间交集计算函数intersection：

int intersection(int a, int b, int c, int d)
{
    return min(b, d) - max(a, c) + 1;
}

计算两个区间[a, b]和[c, d]的交集长度。

（三）主席树操作函数

1. 更新函数update：

void update(int u, int l, int r, int pl, int pr)
{
    tr[u].sum += intersection(l, r, pl, pr);
    if (l >= pl && r <= pr)
    {
        tr[u].add ++ ;
        return;
    }
    int mid = l + r >> 1;
    if (pl <= mid)
    {
        if (!tr[u].l) tr[u].l = ++ idx;
        update(tr[u].l, l, mid, pl, pr);
    }
    if (pr > mid)
    {
        if (!tr[u].r) tr[u].r = ++ idx;
        update(tr[u].r, mid + 1, r, pl, pr);
    }
}

在当前版本的线段树节点中更新指定区间的信息，增加统计值sum，如果当前节点区间包含在更新区间内，则增加懒标记add，并递归更新子树。

1. 修改函数change：

void change(int u, int a, int b, int c)
{
    update(T[u], 1, n, a, b);
    if (L[u] == R[u]) return;
    int mid = L[u] + R[u] >> 1;
    if (c <= mid) change(u << 1, a, b, c);
    else change(u << 1 | 1, a, b, c);
}

在指定版本的线段树中，对指定区间加入一个离散化后的数值c，递归处理子树。

1. 查询区间统计值函数get_sum：

LL get_sum(int u, int l, r, int pl, int pr, int add)
{
    if (l >= pl && r <= pr) return tr[u].sum + (r - l + 1LL) * add;
    int mid = l + r >> 1;
    LL res = 0;
    add += tr[u].add;
    if (pl <= mid)
    {
        if (tr[u].l) res += get_sum(tr[u].l, l, mid, pl, pr, add);
        else res += intersection(l, mid, pl, pr) * add;
    }
    if (pr > mid)
    {
        if (tr[u].r) res += get_sum(tr[u].r, mid + 1, r, pl, pr, add);
        else res += intersection(mid + 1, r, pl, pr) * add;
    }
    return res;
}

查询指定版本线段树中指定区间的统计值，考虑懒标记，递归计算左右子树的统计值并返回。

1. 查询第k大函数query：

int query(int u, int a, int b, int c)
{
    if (L[u] == R[u]) return R[u];
    int mid = L[u] + R[u] >> 1;
    LL k = get_sum(T[u << 1 | 1], 1, n, a, b, 0);
    if (k >= c) return query(u << 1 | 1, a, b, c);
    return query(u << 1, a, b, c - k);
}

在指定版本的线段树中查询指定区间内第c大的数的离散化下标，通过比较右子树的统计值和c的大小，递归在左子树或右子树中查找。

（四）主函数main

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++ )
    {
        scanf("%d%d%d%d", &q[i].op, &q[i].a, &q[i].b, &q[i].c);
        if (q[i].op == 1) nums.push_back(q[i].c);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    build(1, 0, nums.size() - 1);

    for (int i = 0; i < m; i ++ )
    {
        int op = q[i].op, a = q[i].a, b = q[i].b, c = q[i].c;
        if (op == 1) change(1, a, b, get(c));
        else printf("%d\n", nums[query(1, a, b, c)]);
    }

    return 0;
}

1. 读取位置数量n和操作数量m，以及每个操作的信息，将需要离散化的数值存入nums。
2. 对nums进行排序和去重，构建线段树。
3. 循环处理每个操作：
   • 若操作类型为1，调用change函数在指定区间加入数值。
   • 若操作类型为2，调用query函数查询第c大的数，并输出离散化前的数值。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 离散化操作：排序和去重时间复杂度为(O(k\log k))，其中k是需要离散化的数值数量。
• 建树操作：时间复杂度为(O(\log k))。
• 修改操作：每次修改操作涉及线段树的更新，时间复杂度为(O(\log^2 k))。
• 查询操作：每次查询操作需要在主席树中查找，时间复杂度为(O(\log^2 k))。
• 总的时间复杂度为(O(M\log^2 k))，其中M是操作次数。

（二）空间复杂度

主席树的空间复杂度为(O(N\log k))，加上其他辅助数组，总的空间复杂度为(O(N\log k)) ，其中N是位置数量。