线段树、树状数组

建立长度为 $n$，初始所有位置的值为 $1$ 的值域树状数组。将上次出列元素的排名（树状数组中比该元素小的值的数量 $+1$）记为 $las$，初始化 $las=1$。

对于第 $i$ 次出列，从当前排名为 $las$ 的元素向后找 $k-1$ 个元素（因为排名为 $las$ 的元素也报数了）就是本次出列的元素。因为在环上，直接找排名为 $(las+k-2) \bmod (n-i+1) +1$ 的元素编号，使用这个元素更新 $las$ 即可。

使用线段树的做法可以用线段树上二分替代树状数组上倍增。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,k,ans,c[1'000'005];
void add(int x,int y){while(x<=n) c[x]+=y,x+=x&-x;}
int sum(int x){
    int ret=0;
    while(x) ret+=c[x],x-=x&-x;
    return ret;
}
int frank(int x){
    int ret=0;
    for(int i=1<<__lg(n);i;i>>=1) if(ret+i<=n&&c[ret+i]<x) x-=c[ret+=i];
    return ret+1;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) c[i]=i&-i;
    for(int i=1;i<=n;i++){
        static int las=1;
        ans=frank((las+k-2)%(n-i+1)+1);
        las=sum(ans),add(ans,-1);
    }
    printf("%d\n",ans);
    return 0;
}