主席树模版

2025牛客寒假集训营 F，可以用主席树，也可以用树状数组（线段树）+离线处理，并且用树状数组代码更短更好写，只是当时第一次见这种建树思路，没开出来。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=2e5+10;
struct node{
    int l,r;
    int sum;
}tree[N<<5];
#define ls(x) tree[x].l
#define rs(x) tree[x].r
int n,m;
int a[N],b[N],root[N];//root为第i棵线段树的根节点编号
int cnt;
void build(int &x,int l,int r){
    x=++cnt;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
}
void insert(int x,int &y,int l,int r,int v){
    y=++cnt;
    tree[y]=tree[x];
    tree[y].sum++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(v<=mid) insert(ls(x),ls(y),l,mid,v);
    else insert(rs(x),rs(y),mid+1,r,v);
}
int query(int x,int y,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    int s=tree[ls(y)].sum-tree[ls(x)].sum;
    if(k<=s) return query(ls(x), ls(y), l, mid, k);
    else return query(rs(x), rs(y), mid+1, r, k-s);
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int size=unique(b+1,b+1+n)-(b+1);
    build(root[0], 1, size);
    for(int i=1;i<=n;i++){
        int x=lower_bound(b+1,b+1+size,a[i])-b;
        insert(root[i-1],root[i],1,size,x);
    }
    while(m--){
        int x,y,k;
        cin>>x>>y>>k;
        int t=query(root[x-1], root[y], 1, size, k);
        cout<<b[t]<<endl;
    }
    return 0;
}

树状数组+离线处理代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
#define lowbit(x) ((x)&-(x))
int n,m;
const int N=3e5+10;
int a[N];
int tree[N];
int num[N];
int ans[N];
void update(int x,int d,int n){
    while(x<=n){
        tree[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x,int n){
    int ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            a[i]=0;
            tree[i]=0;
            num[i]=0;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
            num[a[i]]=i;
        }
        map<int,vector<array<int,3>>> mp;
        for(int i=1;i<=m;i++){
            int l,r,c;
            cin>>l>>r>>c;
            mp[c].push_back({l,r,i});
        }
        for(int i=1;i<=n;i++){
            int pos=num[i];
            update(pos,1,n);
            if(!mp.count(pos)) continue;
            for(auto v:mp[pos]){
                int l=v[0],r=v[1],tmp=v[2];
                ans[tmp]=sum(r,n)-sum(l-1,n)+l-1;
            }
        }
        for(int i=1;i<=m;i++){
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}