题目描述 Description
有编号从1到N的N个小朋友在玩一种出圈的游戏。开始时N个小朋友围成一圈，编号为I+1的小朋友站在编号为I小朋友左边。编号为1的小朋友站在编号为N的小朋友左边。首先编号为1的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字M时就出圈。直到只剩下1个小朋友，则游戏完毕。
现在给定N,M，求N个小朋友的出圈顺序。
现在给定N,M，求N个小朋友的出圈顺序。
输入描述 Input Description
唯一的一行包含两个整数N,M。（1<=N,M<=30000）
输出描述 Output Description
唯一的一行包含N个整数，每两个整数中间用空格隔开，第I个整数表示第I个出圈的小朋友的编号。
样例输入 Sample Input
5 3
样例输出 Sample Output
3 1 5 2 4
题解：
对于约瑟夫问题我们有很多种姿势去解决
对于求最后的位置有O(n)的
而对于每次的出队位置，可以用线段树O(nlogn)求解
对于这道题：
因为线段树是维护区间信息的数据结构
主要思想就是 根节点0 1 表示是否在圈内 维护一个sum的线段树
当前出圈人是第pos人 下一次是第pos+n-1人 因为刚才pos出去了 所以要-1 为了防止它大于sumv[1] 所以要%sum[1] 又为了防止它是第0个人 所以特判一下
注意是人不是编号 而线段树维护的就是在圈内的人的数量
所以可以递归找到是哪个根节点 然后输出它对应的编号
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx = 30050;
int sum[maxx << 2];
int want, pos;
int num[maxx << 2], rank;
void build(int p, int l, int r)
{
if (l == r)
{
sum[p] = 1;
rank ++;
num[p] = rank;
return ;
}
int mid = (l + r) >> 1;
build (p << 1, l, mid);
build (p << 1 | 1, mid + 1, r);
sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
void del(int p, int l, int r)
{
if (l == r)
{
sum[p] = 0;
cout << num[p] << " ";
return ;
}
int mid = (l + r) >> 1;
if (want <= sum[p << 1])
del(p << 1, l, mid);
else
{
want -= sum[p << 1];
del(p << 1 | 1, mid + 1, r);
}
sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
int main()
{
int n, m;
cin>>n>>m;
m %= n;
if (m == 0)
m = n;
build(1, 1, n);
pos = 1;
while (sum[1])
{
pos = (pos + m - 1) % sum[1];
if (pos == 0)
pos = sum[1];
want = pos;
del (1, 1, n);
}
return 0;
}