登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.8 主席树与可持久化 › 主席树与可持久化 / 搜索
JSON MD

2.8 主席树与可持久化

区间第k小 seg
54 行
CPP JSON
【区间第k小(seg)】 代码包含 update, query, solve 等核心函数,实现了 区间第k小 的算法逻辑。 核心函数: int update(int lu, int l, int r, int x) — 单点/区间更新操作 int query(int u1, int u2, int l, int r, int k) — 区间/路径查询操作 void solve(无参数) — 主解题函数 关键配置: N=2e5 + 5 说明:核心变化:前缀和相减,二分找第 K 小
C++ 54 行 CPP
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5; 
int n, m, cnt, root[N], a[N];
int ls[N << 5], rs[N << 5], w[N << 5];
vector<int> b;
int update(int lu, int l, int r, int x) {
    int u = ++cnt;
    ls[u] = ls[lu]; rs[u] = rs[lu]; w[u] = w[lu] + 1;
    if (l == r) return u;
    int mid = (l + r) >> 1;
    if (x <= mid) ls[u] = update(ls[lu], l, mid, x);
    else rs[u] = update(rs[lu], mid + 1, r, x);
    return u;
}
// 核心变化:前缀和相减,二分找第 K 小
int query(int u1, int u2, int l, int r, int k) {
    if (l == r) return l;
    int d = w[ls[u2]] - w[ls[u1]]; 
    int mid = (l + r) >> 1;
    if (k <= d) return query(ls[u1], ls[u2], l, mid, k); 
    else return query(rs[u1], rs[u2], mid + 1, r, k - d); 
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b.push_back(a[i]);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int max_val = b.size();
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        root[i] = update(root[i - 1], 1, max_val, x);
    }
    
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        int ans_rk = query(root[l - 1], root[r], 1, max_val, k);
        cout << b[ans_rk - 1] << '\n'; 
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}
区间元素数 seg
54 行
CPP JSON
【区间元素数(seg)】 代码包含 update, query, solve 等核心函数,实现了 区间元素数 的算法逻辑。 核心函数: int update(int lu,int l,int r,int x) — 单点/区间更新操作 int query(int u1,int u2,int l,int r,int x) — 区间/路径查询操作 void solve(无参数) — 主解题函数 关键配置: N=1e6+5 说明:#define int long long
C++ 54 行 CPP
#include<iostream>
#include<stack>
#include<string>
#include<set>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
//#define int long long
const int N=1e6+5;
int n,m,cnt,root[N],last[N];
int ls[N<<5],rs[N<<5],w[N<<5];
int update(int lu,int l,int r,int x){
	int u=++cnt;
	ls[u]=ls[lu],rs[u]=rs[lu],w[u]=w[lu];w[u]++;
	if(l==r)return u;
	int mid=(l+r)>>1;
	if(x<=mid)ls[u]=update(ls[lu],l,mid,x);
	else rs[u]=update(rs[lu],mid+1,r,x);
	return u;
}
int query(int u1,int u2,int l,int r,int x){
	if(l>=x)return 0;
	if(r<x)return w[u2]-w[u1];
	int mid=(l+r)>>1;
	return query(ls[u1],ls[u2],l,mid,x)+query(rs[u1],rs[u2],mid+1,r,x);
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(last[x])root[i]=update(root[i-1],0,n,last[x]);
		else root[i]=update(root[i-1],0,n,0);	
		last[x]=i;	
	}
	cin>>m;
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<query(root[l-1],root[r],0,n,l)<<'\n';
	}
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    while(T--)solve();
}
/*
*/
区间MEX seg
46 行
CPP JSON
【区间MEX(seg)】 代码包含 update, query, solve 等核心函数,实现了 区间MEX 的算法逻辑。 核心函数: int update(int pre, int l, int r, int x, int pos) — 单点/区间更新操作 int query(int u, int l, int r, int limit_L) — 区间/路径查询操作 void solve(无参数) — 主解题函数 关键配置: N=2e5 + 5
C++ 46 行 CPP
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
using namespace std;
const int N = 2e5 + 5; 
int n, q, cnt, root[N];
int ls[N * 40], rs[N * 40], min_pos[N * 40]; 
int update(int pre, int l, int r, int x, int pos) {
    int u = ++cnt;
    ls[u] = ls[pre]; rs[u] = rs[pre]; 
    if (l == r) {
        min_pos[u] = pos;
        return u;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) ls[u] = update(ls[pre], l, mid, x, pos);
    else rs[u] = update(rs[pre], mid + 1, r, x, pos);
    min_pos[u] = min(min_pos[ls[u]], min_pos[rs[u]]);
    return u;
}
int query(int u, int l, int r, int limit_L) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (min_pos[ls[u]] < limit_L) return query(ls[u], l, mid, limit_L);
    else return query(rs[u], mid + 1, r, limit_L);
}
void solve() {
    cin >> n >> q;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        if (x > n + 1) {
            root[i] = root[i - 1];
        } else {
            root[i] = update(root[i - 1], 0, n + 1, x, i);
        }
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << query(root[r], 0, n + 1, l) << '\n';
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}
已复制