---

layout: post
title: 洛谷试炼场 4-17 主席树
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 主席树
- 数据结构
- 洛谷

---

P3834 【模板】可持久化线段树 1（主席树）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m,cnt,root[maxn],a[maxn],x,y,k;
struct node{int l,r,sum;}T[maxn*20];
vector<int>v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int l,int r,int &x,int y,int pos){
    T[++cnt]=T[y],T[cnt].sum++,x=cnt;
    if(l==r)return;
    int mid=(l+r)/2;
    if(mid>=pos)update(l,mid,T[x].l,T[y].l,pos);
    else update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k){
    if(l==r)return l;
    int mid=(l+r)/2;
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    if(sum>=k)return query(l,mid,T[x].l,T[y].l,k);
    else return query(mid+1,r,T[x].r,T[y].r,k-sum);
}
template <class T>
inline bool read(T &ret){
    char c;int sgn;if(c=getchar(),c==EOF)return 0;
    while(c!='-'&&(c<'0'||c>'9'))c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9')ret=ret*10+(c-'0');ret*=sgn;return 1;
}
inline void out(int x){if(x>9)out(x/10);putchar(x%10+'0');}
int main()
{
   /* std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);*/
    read(n);read(m);
    for(int i=1;i<=n;i++)read(a[i]),v.push_back(a[i]);
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++)update(1,n,root[i],root[i-1],getid(a[i]));
    while(m--){
       // cin>>x>>y>>k;
       read(x);read(y);read(k);
        out(v[query(1,n,root[x-1],root[y],k)-1]);puts("");
       // cout<<v[query(1,n,root[x-1],root[y],k)-1]<<endl;
    }
    return 0;
}

P2617 Dynamic Rankings (主席树套树状数组)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{int l,r,sum;}s[maxn*20];
vector<int>v;
struct quest{char op;int x,y,k;}Q[maxn];
inline int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
inline int lowbit(int x){return x&(-x);}
int a[maxn],b[maxn],T[maxn];
int n,m;
int tot;
int len;
int temp[2][100],cnt[2];
void update(int &now,int l,int r,int pos,int val){
    if(now==0)now=++tot;
    s[now].sum+=val;
    if(l==r)return;
    int mid=(l+r)/2;
    if(pos<=mid)update(s[now].l,l,mid,pos,val);
    else update(s[now].r,mid+1,r,pos,val);
}
void uptree(int x,int val){
    int pos=get(a[x]);
    for(int i=x;i<=n;i+=lowbit(i))update(T[i],1,len,pos,val);
}
int query(int l,int r,int k){
    if(l==r)return l;
    int x=0,mid=(l+r)/2;
    for(int i=1;i<=cnt[1];i++)x+=s[s[temp[1][i]].l].sum;
    for(int i=1;i<=cnt[0];i++)x-=s[s[temp[0][i]].l].sum;
    if(k<=x){
        for(int i=1;i<=cnt[1];i++)temp[1][i]=s[temp[1][i]].l;
        for(int i=1;i<=cnt[0];i++)temp[0][i]=s[temp[0][i]].l;
        return query(l,mid,k);
    }
    else{
        for(int i=1;i<=cnt[1];i++)temp[1][i]=s[temp[1][i]].r;
        for(int i=1;i<=cnt[0];i++)temp[0][i]=s[temp[0][i]].r;
        return query(mid+1,r,k-x);
    }
}
int qutree(int x,int y,int k){
    memset(temp,0,sizeof(temp));
    cnt[0]=cnt[1]=0;
    for(int i=y;i;i-=lowbit(i))temp[1][++cnt[1]]=T[i];
    for(int i=x-1;i;i-=lowbit(i))temp[0][++cnt[0]]=T[i];
    return query(1,len,k);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],v.push_back(a[i]);
    for(int i=1;i<=m;i++){
        cin>>Q[i].op>>Q[i].x>>Q[i].y;
        if(Q[i].op=='Q')cin>>Q[i].k;
        else v.push_back(Q[i].y);
    }
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    len=v.size();
    for(int i=1;i<=n;i++)uptree(i,1);
    for(int i=1;i<=m;i++){
        if(Q[i].op=='Q')cout<<v[qutree(Q[i].x,Q[i].y,Q[i].k)-1]<<endl;
        else{
            uptree(Q[i].x,-1);
            a[Q[i].x]=Q[i].y;
            uptree(Q[i].x,1);
        }
    }
    return 0;
}

[P3157 CQOI2011]动态逆序对 (主席树套树状数组)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{int l,r,sum;}T[maxn*20];
int a[maxn],p[maxn],c[maxn],uu,pre[maxn],suf[maxn];
int xx[100],yy[100];
int n,m,ooo,rot[maxn];
inline int lowbit(int x){return x&(-x);}
void add(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i))c[i]+=k;
}
int getsum(int x){
    int k=0;
    for(int i=x;i;i-=lowbit(i))k+=c[i];return k;
}
int query(int o,int l,int r,int x,int y){
    if(!o)return 0;
    if(l>=x&&r<=y)return T[o].sum;
    else{
        int mid=(l+r)/2;
        int ans=0;
        if(x<=mid)ans+=query(T[o].l,l,mid,x,y);
        if(mid<y)ans+=query(T[o].r,mid+1,r,x,y);
        return ans;
    }
}
int queryRange(int uu,int vv,int xx,int yy){
    int tmp=0;
    for(int i=uu-1;i;i-=lowbit(i))
        tmp-=query(rot[i],1,n,xx,yy);
    for(int i=vv;i;i-=lowbit(i))
        tmp+=query(rot[i],1,n,xx,yy);
    return tmp;
}
void update(int &rt,int l,int r,int x){
    if(!rt)rt=++ooo;
    T[rt].sum++;
    if(l==r)return;
    int mid=(l+r)/2;
    if(x<=mid)update(T[rt].l,l,mid,x);
    if(mid<x)update(T[rt].r,mid+1,r,x);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[a[i]]=i;
        pre[i]=getsum(n)-getsum(a[i]);
        ans+=pre[i];
        add(a[i],1);
    }
    memset(c,0,sizeof(c));
    for(int i=n;i>=1;i--){
        suf[i]=getsum(a[i]-1);
        add(a[i],1);
    }
    while(m--){
        cout<<ans<<endl;
        cin>>uu;
        uu=p[uu];
        ans-=pre[uu]+suf[uu];
        ans+=queryRange(1,uu-1,a[uu]+1,n);
        ans+=queryRange(uu+1,n,1,a[uu]-1);
        for(int i=uu;i<=n;i+=lowbit(i))
            update(rot[i],1,n,a[uu]);
    }
    return 0;
}