LA 3882 And Then There Was One

この問題はジョセフリングの問題だが、データが強化されただけだ.
削除シーケンスを求める必要はなく、削除した最後の数字を要求するだけで、
だからプッシュする方法とセグメントツリーがあります

#include <stdio.h>
#include <string.h>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
const int maxn = 1000005;
int cnt[maxn << 3];
void Build ( int l, int r, int rt )
{
    cnt[rt] = r-l+1;
    if ( l == r )
        return ;
    int m = ( l+r ) >> 1;
    Build ( lson );
    Build ( rson );
}
void PushUP ( int rt )
{
    cnt[rt] = cnt[rt << 1]+cnt[rt << 1 | 1];
}
void update ( int q, int l, int r, int rt )
{
    if ( l == r )
    {
        cnt[rt] = 0;
        return ;
    }
    int m = ( l+r ) >> 1;
    if ( q <= cnt[rt << 1] )
        update ( q, lson );
    else
        update ( q-cnt[rt << 1], rson );
    PushUP ( rt );  // 
}
int query ( int q, int l, int r, int rt )
{
    if ( l == r )
        return l;
    int m = ( l+r ) >> 1;
    if ( q <= cnt[rt << 1] )
        return query ( q, lson );
    else
        return query ( q-cnt[rt << 1], rson );
}
int main ( )
{
    int n, k, m;
    while ( ~ scanf ( "%d%d%d", &n, &k, &m ) && n )
    {
        memset ( cnt, 0, sizeof ( cnt ) );
        Build ( 1, n, 1 );
        for ( int i = n-1; i >= 1; i -- )   //n-1 
        {
            update ( m, 1, n, 1 );
            m = ( m+k-2+i )%i+1;    // 
            //printf ( "%d
", m );
        }
        printf ( "%d
", query ( 1, 1, n, 1 ) );    // 
    }
    return 0;
}

.