题目一:

　　大意

　　求静态区间第k小.

　　主要思想:

　　　　利用主席树前缀和思想,对序列先离散得序列${b}$,然后第$i$个版本的主席树表示区间$[1,i]$上各个元素出现的次数.先建颗空树,一一插入,每次update继承原版本的节点信息,rt[i]用以记录区间[1,i]的线段树根作为入口,然后根据需求进行单点修改即可.$sum$可以看作前缀和,当我们要查询$[x,y]$上的各元素出现次数,可以用区间$[1,y]$与区间[1,x-1]作差,然后根据需求统计答案即可.

　　code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define R register
#define debug puts("mlg")
#define next exjfasaslfasfadfsaf
#define maxn 210000
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();    
inline void write(ll x);
inline void writesp(ll x);
inline void writeln(ll x);
ll n,m;
ll a[maxn],b[maxn],rt[maxn<<5],ls[maxn<<5],rs[maxn<<5],sum[maxn<<5],cnt;
ll p;
inline void build(ll &Rt,ll l,ll r){
    Rt=++cnt;
    if(l==r) return;
    ll mid=l+r>>1;
    build(ls[Rt],l,mid);build(rs[Rt],mid+1,r);
}

inline ll update(ll fa,ll l,ll r){
    ll Rt=++cnt;
    ls[Rt]=ls[fa];rs[Rt]=rs[fa];sum[Rt]=sum[fa]+1;
    if(l==r) return Rt;
    ll mid=l+r>>1;
    if(p<=mid) ls[Rt]=update(ls[Rt],l,mid);
    else rs[Rt]=update(rs[Rt],mid+1,r);
    return Rt;
}

inline ll query(ll u,ll v,ll l,ll r,ll k){
    ll mid=l+r>>1,x=sum[ls[v]]-sum[ls[u]];
    if(l==r) return l;
    if(k<=x) return query(ls[u],ls[v],l,mid,k);
    else return query(rs[u],rs[v],mid+1,r,k-x);
}
ll q;
int main(){
    n=read();m=read();
    for(R ll i=1;i<=n;i++) a[i]=b[i]=read();
    sort(b+1,b+n+1);    
    q=unique(b+1,b+n+1)-b-1;
    build(rt[0],1,q);
    for(R ll i=1;i<=n;i++){
        p=lower_bound(b+1,b+q+1,a[i])-b;
        rt[i]=update(rt[i-1],1,q);
    }
    while(m--){
        ll l=read(),r=read(),k=read();
        writeln(b[query(rt[l-1],rt[r],1,q,k)]);
    }
} 
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}

题目二:

　　大意:

　　　　今有一序列与若干操作.操作细分二种,其一为修改某历史版本某位置值作为新版本,其二为查询某历史版本某位置值并copy该版本作为新版本,试问每次查询输出数有几何.

　　solution:

　　　　此题较容易,不必利用前缀和思想,无需离散,修改正常改,查询正常查,新版本直接使新根与该版本根相同即可.

　　code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define R register
#define next bmdsaljdk
#define debug puts("mlg")
#define maxn 1100000
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writeln(ll x);
inline void writesp(ll x);
ll n,m;
ll a[maxn],ls[maxn<<5],rs[maxn<<5],num[maxn<<5],cnt,rt[maxn<<5];
ll tot;
inline void build(ll &Rt,ll l,ll r){Rt=++cnt;if(l==r){num[Rt]=a[l];return;}ll mid=l+r>>1;build(ls[Rt],l,mid);build(rs[Rt],mid+1,r);} 

inline ll update(ll fa,ll l,ll r,ll p,ll q){ll Rt=++cnt;ls[Rt]=ls[fa];rs[Rt]=rs[fa];if(l==r){num[Rt]=q;return Rt;}ll mid=l+r>>1;if(p<=mid) ls[Rt]=update(ls[Rt],l,mid,p,q);else rs[Rt]=update(rs[Rt],mid+1,r,p,q);return Rt;}

inline ll query(ll v,ll l,ll r,ll p){if(l==r) return num[v];ll mid=l+r>>1;if(p<=mid) return query(ls[v],l,mid,p);else return query(rs[v],mid+1,r,p);}

int main(){
    n=read();m=read();
    for(R ll i=1;i<=n;i++) a[i]=read();
    build(rt[0],1,n);
    while(m--){
        ll v=read(),type=read(),pos=read();
        if(type==1){
            ll val=read();
            rt[++tot]=update(rt[v],1,n,pos,val);
        }
        else{
            rt[++tot]=rt[v];
            writeln(query(rt[v],1,n,pos));
        }    
    }
}
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}