P3834 【模板】可持久化线段树 2 _生活百科

P3834主席树模板，求区间第k小。
【P3834 【模板】可持久化线段树 2】 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define lc tr[i].ch[0] 4 #define rc tr[i].ch[1] 5 #define Lc tr[j].ch[0] 6 #define Rc tr[j].ch[1] 7 #define mid ((l + r) >> 1) 8 const int N = 2e5 + 10; 9 int n, m, a[N], b[N];10 int cnt, rt[N];11 struct node {12int num, ch[2];13 }tr[N * 20];14 void update(int &i, int j, int l, int r, int k) {15i = ++cnt;//编号16tr[i] = tr[j];//复制之前版本17++ tr[i].num;18if (l == r) return ;19if (k <= mid) update(lc, Lc, l, mid, k);20else update(rc, Rc, mid + 1, r, k);21 }22 int query(int i, int j, int l, int r, int k) {23if (l == r) return l;//返回下标24int s = tr[Lc].num - tr[lc].num;25if (k <= s) return query(lc, Lc, l, mid, k);26else return query(rc, Rc, mid + 1, r, k - s);27 }28 int main() {29scanf("%d %d", &n, &m);30for (int i = 1; i <= n; i ++) {31scanf("%d", &a[i]);32b[i] = a[i];33}34sort(b + 1, b + n + 1);35int tot = unique(b + 1, b + n + 1) - b - 1;36cnt = 0, rt[0] = 0;37for (int i = 1; i <= n; i ++)38update(rt[i], rt[i - 1], 1, tot, lower_bound(b + 1, b + tot + 1, a[i]) - b);39int x, y, k;40while (m --) {41scanf("%d %d %d", &x, &y, &k);42printf("%d\n", b[query(rt[x - 1], rt[y], 1, tot, k)]);43}44return 0;45 }

P3834 【模板】可持久化线段树 2

推荐阅读

白羊座最适合的运动

职工医保和城乡居民医保哪个划算？交哪个好

关于来不及诉说简述来不及诉说

形容教室里很多人的成语

肉煎饺的做法步骤肉煎饺的做法步骤

越在乎你才会越嫌弃你的星座，天蝎上榜！

伊美婷成分伊美婷胶原蛋白安全吗

保护视力的绘画作品保护视力的绘画作品画法

属兔的适合住什么楼层最好住几楼大吉？

攀升MaxBook P2参数_攀升MaxBook P2配置

荞麦茶的功效有哪些荞麦茶有什么作用功效

铝锅煮汤对人体有害吗，不建议经常使用铝锅煮汤

发朋友圈运动的幽默句子发朋友圈运动句子

《四季豆一定要焯水吗》

王丽云主演的电视剧有哪些王丽云演的全部电视剧

大连金普新区文旅场馆7月19日起取消查验核酸报告

江苏省公务员abc类区别江苏省公务员abc类的区别

电脑版微信怎么发朋友圈电脑版微信怎么发朋友圈视频

芋头和香芋一样吗？芋头什么人不能多吃

鱼鳞痣怎么祛除掉鱼鳞痣怎么祛除