123 lines
4.9 KiB
C++
123 lines
4.9 KiB
C++
// http: // poj.org/problem?id=2104
|
||
//#include <bits/stdc++.h>
|
||
#include <iostream>
|
||
#include <string.h>
|
||
#include <stdio.h>
|
||
#include <vector>
|
||
#include <map>
|
||
#include <queue>
|
||
#include <algorithm>
|
||
#include <math.h>
|
||
#include <cstdio>
|
||
|
||
const int N = 100010;
|
||
using namespace std;
|
||
|
||
//建立一颗权值线段树，每个点存储的信息为该值域区间存在的数的个数
|
||
struct Node {
|
||
int l, r; //分别表示左右节点编号
|
||
int cnt; //区间内数字个数
|
||
} tr[N * 4 + N * 17]; //初始骨架N * 4 再加上最多M次插入一共修改MlogM个节点
|
||
//也见过有的大佬说，直接开N*32就行
|
||
|
||
vector<int> nums; //用于离散化的数组,由于数的范围很大，但是不能开那么大的空间，所以需要离散化
|
||
int root[N], idx; // root记录根节点的版本号【root[r]表示插入了第r个数版本的线段树】, idx记录树节点的版本号
|
||
int a[N]; //原始数组
|
||
int n, m;
|
||
|
||
//离散化二分查找
|
||
int find(int x) {
|
||
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
|
||
}
|
||
|
||
//构建新版本的线段树,返回新创建的节点号
|
||
//注意里与普通版本的线段树不一样，普通线段树是的左儿子编号是父亲的编号*2，右儿子的编号是父亲的编号*2+1
|
||
//而主席树的节点编号是通过tot++随用随算的，因为多个版本，不能沿用原来的处理办法，那样就空着内存节点的太多了
|
||
int build(int l, int r) { // l,r是指数据管辖区间
|
||
int p = ++idx; //生成节点号
|
||
if (l == r) return p; //到叶子节点,直接返回新产生的节点号，不再递归
|
||
int mid = (l + r) >> 1; // 2x,2x+1，静态线段树构建办法
|
||
tr[p].l = build(l, mid); //构建左子树
|
||
tr[p].r = build(mid + 1, r); //构建右子树
|
||
return p;
|
||
}
|
||
|
||
/**
|
||
* @brief 对原始数据，通过一个一个的insert方式存入主席树，以达到生成每个版本线段树的目标
|
||
*
|
||
* @param p 上一个版本的版本号
|
||
* @param l
|
||
* @param r
|
||
* @param x
|
||
* @return int
|
||
*/
|
||
int insert(int p, int l, int r, int x) {
|
||
int q = ++idx; // 1、获取到可用节点编号
|
||
tr[q] = tr[p]; // 2、旧版本啥样我啥样
|
||
if (l == r) { // 3、第x大位置的数字个数增加了1个
|
||
tr[q].cnt++;
|
||
return q;
|
||
}
|
||
int mid = (l + r) >> 1;
|
||
if (x <= mid) // 4、x小于等于mid，向左半部递归
|
||
tr[q].l = insert(tr[p].l, l, mid, x);
|
||
else // 5、x大于mid,向右半部递归
|
||
tr[q].r = insert(tr[p].r, mid + 1, r, x);
|
||
|
||
//更新区间内数字个数,相当于pushup
|
||
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
|
||
return q; //返回新创建的节点编号
|
||
}
|
||
/**
|
||
* @brief 在q这个版本的线段树中，它的前序版本是p，管辖范围是[l,r],求第k小数
|
||
*
|
||
* @param q 当前版本号
|
||
* @param p 前序版本号
|
||
* @param l 左边界
|
||
* @param r 右边界
|
||
* @param k 第k小
|
||
* @return int 是什么数字
|
||
*/
|
||
int query(int q, int p, int l, int r, int k) {
|
||
if (l == r) return r; //到叶子节点了，返回是第l个数字，nums返回原始数字
|
||
//当前版本左儿子区间内的数字个数，减去，前序版本左儿子区间内的数字个数，
|
||
//描述了在从l到r这两个版本间增加的数字数量，类似于前缀和思想
|
||
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
|
||
int mid = (l + r) >> 1;
|
||
if (k <= cnt)
|
||
return query(tr[q].l, tr[p].l, l, mid, k);
|
||
else
|
||
return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
|
||
}
|
||
|
||
int main() {
|
||
cin >> n >> m;
|
||
for (int i = 1; i <= n; i++) {
|
||
cin >> a[i];
|
||
nums.push_back(a[i]);
|
||
}
|
||
//离散化 为什么要离散化？是因为值域范围1e9，太大
|
||
sort(nums.begin(), nums.end());
|
||
nums.erase(unique(nums.begin(), nums.end()), nums.end());
|
||
|
||
//构建版本0,只有版本0需要构建
|
||
//因为离散化后的范围区间是0~nums.size()-1
|
||
//看来构建线段树的l,r其实是指的原始数组的索引位置
|
||
root[0] = build(0, nums.size() - 1);
|
||
|
||
//构建不同版本的线段树
|
||
for (int i = 1; i <= n; i++)
|
||
// 1、每个新版本，都只能在上一个版本基础上进行修改获取到
|
||
// 2、现在这个新版本，也和上一个版本的范围是一样的，也是[0,nums.size()-1]
|
||
// 3、find(a[i])：通过二分获取a[i]这个数据现在离散化后所在的位置
|
||
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
|
||
|
||
while (m--) {
|
||
int l, r, k;
|
||
cin >> l >> r >> k;
|
||
//查询[l,r]区间中的第k大数，利用前缀和的思想,从[l ~ r]中的数据剔除掉[1 ~ l-1]的数据,
|
||
//不同版本的线段树的结构都是一样的，所以初始都是从0到nums.size()这个范围当中找
|
||
printf("%d\n", nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)]);
|
||
}
|
||
return 0;
|
||
} |