约瑟夫问题(线段树） - c++编程基础

// File Name: wiki1282.cpp   
// Author: bo_jwolf   
// Created Time: 2013年08月17日 星期六 10时24分52秒   
  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
  
using namespace std;  
#define maxn 30005   
#define lson l , m , rt << 1    
#define rson m + 1 , r , rt << 1 | 1    
int sum[ maxn << 2 ] ;  
void PushUp( int rt )  
{  
    sum[ rt ] = sum[ rt << 1 ] + sum[ rt << 1 | 1 ] ;  
}  
  
void build( int l , int r , int rt )  
{  
    sum[ rt ] = r - l + 1 ;  
    if( l == r )  
        return ;  
    int m = ( l + r ) >




>  1 ;  
    build( lson ) ;  
    build( rson ) ;  
}  
  
int query( int p , int l , int r , int rt )  
{  
    if( l == r )  
    {  
        sum[ rt ] = 0 ;  
        return l ;  
    }  
    int m = ( l + r ) >> 1 ;  
    int ans  ;  
    if( sum[ rt << 1 ] >= p )  
        ans =  query( p , lson ) ;  
    else  
        ans = query( ( p - sum[ rt << 1 ] ) , rson ) ;  
    PushUp( rt ) ;  
    return ans ;  
}  
  
int main()  
{  
    int n , k ;  
    cin >> n >> k ;  
    build( 1 , n , 1 ) ;  
    int temp = k ;  
    for( int i = 1 ; i <= n ; ++i )  
    {  
        if( i != n )  
            cout << query( temp , 1 , n , 1 ) << " ";  
        else  
            cout << query( temp , 1 , n , 1 ) ;  
        if( i != n )  
            temp = ( temp + k - 1 ) % ( n - i ) ;  
        if( temp == 0 )  
            temp = n - i ;  
    }  
return 0;  
}