POJ 2886 Who Gets the Most Candies? セグメントツリー

http://poj.org/problem?id=2886
タイトル:
N人は1つのゲームを游んで、すべての人はすべて1つのweightがあって、ゲームは第K人から始めて、第1ラウンドのマークがKの人はゲームを脱退して、次の脱退する人の番号は前のラウンドの脱退する人のweightから决めて、もし前のラウンドの脱退する人のweightは
正のため、次の脱退者は前回脱退した人の左手のweight個人で、負数なら右手で
の第weight個人、すべての人が退出する時すべて1つの得点があって、得点は退出する番号の約数の個数で、得点に最も聞きます
高い人は何点か得られる.N <= 500.000
考え方:
問題を分析すると、まず問題が最も得点の高い人の得点を要求していることがわかります.そのため、私たちはまずすべての編を前処理することができます.
番号の得点、そして最大の得点を求めると、問題は指定された退出番号を求める人になります.そしてそれぞれに
人はweightを持っていて、今私たちがしなければならないのはどのように迅速に一人から別の人を求めて、このように私たちは利益を得ることができます
線分木で求め,N<=500,000の場合,これはO(nlogn)のアルゴリズム内で求めることができる. 
コード:

#include <stdio.h>
#include <string.h>
#define LL(a) ( (a)<<1 )
#define RR(a) ( (a)<<1|1 )

int N , K ;
const int MAXN = 500010 ;
char name[MAXN][11] ;
int val[MAXN] ;
int d_num[MAXN] ;
int _max  , pos ;
int num[MAXN<<2] ;

void cal(){
    for(int i=1;i<MAXN;i++)
        d_num[i] = 1 ;
    for(int i=2;i<MAXN;i++){
        for(int j=1;j*i<MAXN;j++){
            d_num[ i*j ] ++ ;
        }
    }
}
void build(int l , int r , int idx ){
    int mid = (l + r) >> 1 ;
    if(l == r){
        num[idx] = 1 ;
        return ;
    }
    build(l , mid , LL(idx) ) ;
    build(mid+1, r , RR(idx) ) ;
    num[idx] = num[ LL(idx) ] + num[ RR(idx) ] ;
}
int query(int l ,int r, int idx , int a , int b){
    if(l==a && r==b){
        return num[idx] ;
    }
    int mid = (l + r) >> 1;
    if(b <= mid){
        return query( l, mid, LL(idx) , a, b);
    }
    else if( mid < a ){
        return query( mid+1 , r ,RR(idx) , a ,b );
    }
    else{
        return query( l ,mid ,LL(idx) , a , mid ) + query( mid+1, r, RR(idx) , mid+1, b );
    }
}
void update1(int l,int r , int idx ,int pos){
    if(l == r){
        num[idx] -- ;
        return  ;
    }
    int mid = (l + r) >> 1;
    if( pos <= mid ){
        update1(l , mid , LL(idx) , pos );
    }
    else{
        update1(mid+1, r,  RR(idx) , pos );
    }
    num[idx] = num[ LL(idx) ] + num[ RR(idx) ] ;
}
int update(int l ,int r , int idx , int vv){
    if(l == r){
        return l ;
    }
    int mid = (l + r ) >> 1 ;
    if( num[ LL(idx) ] >= vv ){
        return update(l ,mid , LL(idx) , vv);
    }
    else{
        return update(mid+1, r , RR(idx) , vv-num[ LL(idx) ] ) ;
    }
}

void solve(){
    int nn = 1 ;
    int now = K ;

    while( nn <= N ){
        if(nn == pos){
            printf("%s %d
",name[now] , d_num[pos] );
            return ;
        }
        int vv = val[now] ;
        int left = N - nn ;
        int n1 , n2 ;
        if( vv > 0 ){
            // go left
            n1 = query(1, N , 1 , 1 , now );
            update1(1 , N ,1 , now);
            n1 -- ;
            n2 = left - n1 ;
            vv %= left ;
            if( vv == 0 ){
                if(n1 == 0)
                    now = update(1 , N ,1 , left) ;
                else
                    now = update(1, N ,1 , n1 ) ;
            }
            else{
                if( vv <= n2 ){
                    vv = n1 + vv ;
                }
                else{
                    vv -= n2 ;
                }
                now = update(1, N , 1 , vv );
            }
        }
        else{
            // go right ;
            n1 = query(1 , N , 1 , 1 , now ) ;
            update1(1 , N ,1 , now);
            n1 --  ;
            n2 = left - n1 ;
            vv = -vv ;
            vv %= left ;
            if( vv == 0 ){
                if( n2 == 0 ){
                    now = update(1 , N ,1 , 1 );
                }
                else{
                    now = update(1 , N , 1 , n1 + 1 );
                }
            }
            else{
                if( vv <= n1 ){
                    now = update(1, N ,1 ,n1+1-vv);
                }
                else{
                    now = update(1 , N ,1 , left-(vv-n1)+1 );
                }
            }
        }
        nn++ ;
    }
}

int main(){
    cal() ;
    //freopen("1out.txt","w",stdout) ;
    while( scanf("%d %d",&N,&K) == 2){
        for(int i=1;i<=N;i++){
            scanf("%s %d",name[i] , val+i) ;
        }
        _max = -1 ;
        for(int i=1;i<=N;i++){
            if( d_num[i] > _max ){
                _max = d_num[i] ;
                pos = i ;
            }
        }
        build( 1, N ,1 );
        solve() ;
    }
    return 0 ;
}