# 主席树模板

• 2018-03-04
• 0
• 0

## Code: O((N+M)logN) [41832KB,868MS]

```// 主席树 (2018.3.4)
// 洛谷 3834 【模板】可持久化线段树 1（主席树）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 200005
#define MAXNODE 3600005
using namespace std;

inline void getint(int &num){
char ch; bool neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
if(neg) num = -num;
}

int N, M, a[MAXN], disc[MAXN];
int rt[MAXN], sz[MAXNODE], lc[MAXNODE], rc[MAXNODE];

inline int newNode(int s, int l, int r){
static int topp = 0;
sz[++topp] = s, lc[topp] = l, rc[topp] = r;
}

inline int build(int l, int r){
int u = newNode(0, 0, 0);
if(l == r) return u;
int mid = l + r >> 1;
if(l <= mid) lc[u] = build(l, mid);
if(mid < r) rc[u] = build(mid + 1, r);
return u;
}

inline void add(int &u, int pred, int l, int r, int v){
u = newNode(sz[pred] + 1, lc[pred], rc[pred]);
if(l == r) return;
int mid = l + r >> 1;
if(v <= mid) add(lc[u], lc[pred], l, mid, v);
else add(rc[u], rc[pred], mid + 1, r, v);
}

inline int query(int tot, int del, int l, int r, int k){
if(l == r) return l;
int mid = l + r >> 1, cnt = sz[lc[tot]] - sz[lc[del]];
if(k <= cnt) return query(lc[tot], lc[del], l, mid, k);
else return query(rc[tot], rc[del], mid + 1, r, k - cnt);
}

int main(){
getint(N), getint(M);
for(register int i = 1; i <= N; i++) getint(a[i]), disc[i] = a[i];
sort(disc + 1, disc + N + 1);
int K = unique(disc + 1, disc + N + 1) - disc - 1;
for(register int i = 1; i <= N; i++) a[i] = lower_bound(disc + 1, disc + K + 1, a[i]) - disc;
rt[0] = build(1, K);
for(register int i = 1; i <= N; i++) add(rt[i], rt[i - 1], 1, K, a[i]);
for(register int i = 1; i <= M; i++){
int l, r, k; getint(l), getint(r), getint(k);
int res = query(rt[r], rt[l - 1], 1, K, k);
printf("%d\n", disc[res]);
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai