学步园

http://poj.org/problem?id=2104 

入门的划分树，说实话一开始看着挺晕的，真看明白了，知道了各个操作各个变量的意义就简单多了。

这个有没有线段树的解法？既然是基于线段树的，那么处理这种问题就应该比线段树的复杂度低很多吧。

code:

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <list>
#include <ctime>
using namespace std ;
#define SET(arr, what)  memset(arr, what, sizeof(arr))
#define FF(i, a)        for(i=0; i<a; i++)
#define SD(a)           scanf("%d", &a)
#define SSD(a, b)       scanf("%d%d", &a, &b)
#define SF(a)           scanf("%lf", &a)
#define SS(a)           scanf("%s", a)
#define SLD(a)          scanf("%lld", &a)
#define PF(a)           printf("%d\n", a)
#define PPF(a, b)       printf("%d %d\n", a, b)
#define SZ(arr)         (int)a.size()
#define SWAP(a,b)       a=a xor b;b= a xor b;a=a xor b;
#define read            freopen("in.txt", "r", stdin)
#define write            freopen("out.txt", "w", stdout)
#define MAX             1<<30
#define ESP             1e-5
#define lson            l, m, rt<<1
#define rson            m+1, r, rt<<1|1
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline void AMin(T &a,T b){if(a==-1||a>b)a=b;}
template<class T> inline void AMax(T &a,T b){if(a<b)a=b;}
template<class T> inline T Min(T a,T b){return a>b?b:a;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
const int MAXN = 100010 ;
int data[30][MAXN], sorted[MAXN], toleft[30][MAXN] ;
int cmp(const void *a, const void *b){
    return *(int *)a < *(int *)b ? -1 : 1 ;
}
void build(int l, int r, int d){
    if(l==r)    return ;
    int i ;
    int m = (l + r) >> 1 ;
    int ls = m - l + 1 ;
    for(i=l; i<=r; i++) if(data[d][i]<sorted[m])    ls -- ;
    int lp = l ;
    int rp = m + 1 ;
    for(i=l; i<=r; i++){
        if(i==l)    toleft[d][i] = 0 ;
        else        toleft[d][i] = toleft[d][i-1] ;
        if(data[d][i]<sorted[m]){
            toleft[d][i] ++ ;
            data[d+1][lp++] = data[d][i] ;
        }else if(data[d][i]>sorted[m])
            data[d+1][rp++] = data[d][i] ;
        else{
            if(ls){
                ls -- ;
                toleft[d][i] ++ ;
                data[d+1][lp++] = data[d][i] ;
            }else data[d+1][rp++] = data[d][i] ;
        }
    }
    build(l, m, d+1) ;
    build(m+1, r, d+1) ;
}
int query(int L, int R, int k, int l, int r, int d){
    if(L==R)    return data[d][L] ;
    int m = (l + r) >> 1 ;
    int lLR, llL, rLR, rlL ;
    if(L==l){
        lLR = toleft[d][R] ;
        llL = 0 ;
    }else{
        lLR = toleft[d][R] - toleft[d][L-1] ;
        llL = toleft[d][L-1] ;
    }
    int nl, nr ;
    if(lLR>=k){
        nl = l + llL ;
        nr = l + lLR + llL - 1 ;
        return query(nl, nr, k, l, m, d+1) ;
    }else{
        rlL = L - l - llL ;
        rLR = R - L + 1 - lLR ;
        nl = m + 1 + rlL ;
        nr = m + rlL + rLR ;
        return query(nl, nr, k-lLR, m+1, r, d+1) ;
    }
}
int main(){
    int n, m, i, j, l, r, k ;
    while(~SSD(n, m)){
        for(i=1; i<=n; i++){
            SD(data[0][i]) ;
            sorted[i] = data[0][i] ;
        }
        qsort(sorted+1, n, sizeof(int), cmp) ;
        build(1, n, 0) ;
        while(m--){
            scanf("%d%d%d", &l, &r, &k) ;
            PF(query(l, r, k, 1, n, 0)) ;
        }
    }
    return 0 ;
}