主席树（静态）

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int>v;
struct node{
    int l;
    int r;
    int cnt;
}tr[3e6+10];
int n;
int get(int x)
{
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void pushup(int u)
{
    tr[u].cnt=tr[tr[u].l].cnt+tr[tr[u].r].cnt;
}
int build(int l,int r)
{
    int u=++idx;    
    if(l==r)    return ;
    int mid=l+r>>1;
    tr[u].l=build(l,mid);
    tr[u].r=build(mid+1,r);

    return u;
}
int insert(int p,int &q,int l,int r,int x)
{
    if(!q)    q=++idx;
    if(l==r)
    {
        tr[q].cnt++;
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid)




    pushup(p);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        v.push_back(a[i]);
    }
    root[0]=build(1,v.size());

    for(int i=1;i<=n;i++)
    {
        root[i]=insert(root[i-1],root[i],1,v.size(),get(a[i]));
    }
    return 0;
}