主席树入门

板子题: 静态区间rankk。。

首先考虑建立一棵权值线段树。如果在权值线段树上求整个区间的rankk是非常简单的

但是如果求的不是整个区间而是一个静态区间呢?

我们发现rankk操作是可减的。如果我们可以快速求出[1,r]和[1,l]的个数的差就可以求出rankk

既然要求[1,r]和[1,l],非常容易想到权值线段树动态加点。但是我们在加入r这个位置的时候还需要访问l这个时刻的树。

于是考虑对线段树可持久化,这样就可以快速访问历史版本。首先把1到n的数字依次加入这课主席树,然后每次询问只需要访问加入l和加入r的两个版本的数字差就好。

说的不是很清楚啊

怎么做到可持久呢

当然,如果可以树状数组就更方便,但是貌似不好可持久(巨佬们说可以可持久但是我不会网上也没教程)

考虑可持久权值线段树。

由于是单点修改,每一次只修改从根到叶子的一个路径,修改只用了logn的空间。所以可以考虑把每次修改后的路径给存一下。

于是空间需要$O(n+qlogn+eps)$这么大

代码:

/*Heroes Never Die!*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200006

int id,cnt , sum[MAXN*21] , ls[MAXN*21], rs[MAXN*21] , rt[MAXN*21];

void build( int& k ,int l ,int r ) {
    k = ++id;
    if( l == r ) return;
    int m = l + r >> 1;
    build( ls[k], l , m ) , build( rs[k], m + 1 , r );
}
void change( int old , int& k , int l , int r , int p , int x ) {
    k = ++id , ls[k] = ls[old] , rs[k] = rs[old];
    sum[k] = sum[old] + x;
    if( l == r ) return;
    int m = l + r >> 1;
    if( p <= m ) change( ls[old] , ls[k] , l , m , p , x );
    else change( rs[old] , rs[k] , m + 1 , r , p , x );
}
int query( int old , int cur , int l , int r , int k ) {
    if( l == r ) return l;
    int cursum = sum[ls[cur]] - sum[ls[old]] , m = l + r >> 1;
    if( cursum >= k ) return query( ls[old] , ls[cur] , l,m,k );
    else return query( rs[old],rs[cur],m+1,r,k-cursum );
} 

int n , A[MAXN] , idx[MAXN] , m;
int main() {
    //freopen("input","r",stdin);
    cin >> n >> m;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]) , idx[i] = A[i];
    sort( idx + 1 , idx + 1 + n );
    cnt = unique( idx + 1 , idx + 1 + n ) - idx - 1;
    build( rt[0] , 1 , cnt );
    for( int i = 1 ; i <= n ; ++ i ) 
        A[i] = lower_bound( idx + 1, idx + cnt + 1 , A[i] ) - idx;
    for( int i = 1; i <= n ;++ i ) change( rt[i-1] , rt[i] , 1,cnt,A[i],1 );
    for( int i = 1,u,v,k ; i <= m ; ++ i ) 
        scanf("%d%d%d",&u,&v,&k) , printf("%d\n",idx[query(rt[u-1],rt[v],1,cnt,k)]); 
}