約瑟夫問題(線段樹）

// File Name: wiki1282.cpp   
// Author: bo_jwolf   
// Created Time: 2013年08月17日 星期六 10時24分52秒   
  
#include<vector>   
#include<list>   
#include<map>   
#include<set>   
#include<deque>   
#include<stack>   
#include<bitset>   
#include<algorithm>   
#include<functional>   
#include<numeric>   
#include<utility>   
#include<sstream>   
#include<iostream>   
#include<iomanip>   
#include<cstdio>   
#include<cmath>   
#include<cstdlib>   
#include<cstring>   
#include<ctime>   
  
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;  
}