codevs1282 约瑟夫问题(线段树)

题目描述 Description

有编号从1到N的N个小朋友在玩一种出圈的游戏。开始时N个小朋友围成一圈，编号为I+1的小朋友站在编号为I小朋友左边。编号为1的小朋友站在编号为N的小朋友左边。首先编号为1的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字M时就出圈。直到只剩下1个小朋友，则游戏完毕。

现在给定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

N是30000，直接模拟得TLE。

分析一下，我们有以下两种操作：

1．找到剩余队列中第i个人在数组中的位置

2．删除第i个人

假如我们一开始给每个人一个权值1，然后维护一个前缀和s(n)那么，操作1就变成了找到前缀和为i的位置。当将第i个人删除时，只需将其权值置0，维护好前缀和，这样剩余队列中第i’个人的实际位置就在原先第i人后面了。

能快速进行上述操作的一种数据结构就是线段树。

线段树单点修改维护区间和不复杂。

现在说怎么找第i个人的实际位置。

对线段树上任意非叶子结点，加入它左子树维护的区间和小于等于i，那么就递归的向左子树找第i人的位置，否则，向右子树递归的找(i-sum(lc))，其中sum(lc)表示左子树维护的一段区间和。

当递归到叶子结点时，该结点的区间标记(我代码中的L和R)就是我们要找的位置。

有了这个数据结构，我们就可以模拟了。

#include<iostream>
#include<cassert>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<iterator>
#include<cstdlib>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define debug(x) cout<<"debug "<<x<<endl;
#define rep(i,f,t) for(int i = (f),_end_=(t); i <= _end_; ++i)
#define rep2(i,f,t) for(int i = (f),_end_=(t); i < _end_; ++i)
#define dep(i,f,t) for(int i = (f),_end_=(t); i >= _end_; --i)
#define dep2(i,f,t) for(int i = (f),_end_=(t); i > _end_; --i)
#define clr(c, x) memset(c, x, sizeof(c) )
typedef long long int64;
const int INF = 0x5f5f5f5f;
const double eps = 1e-8;


//*****************************************************
const int maxn = 30005;
#define MID int mid = (L + R)>>1;
#define CHILDEN int lc = node<<1, rc = node<<1|1;

struct sgt
{
	int T[maxn<<2];
	void build(int node,int L,int R){
		if(L == R)T[node] = 1;
		else{
			MID;CHILDEN;
			build(lc,L,mid);
			build(rc,mid+1,R);
			T[node] = T[lc]+T[rc];
		}
	}
	void update(int pos,int node,int L,int R){
		if(L == R){
            assert(pos == L);
			T[node] = 0;
		}else{
			MID;CHILDEN;
			if(pos <= mid)
				update(pos,lc,L,mid);
			else
				update(pos,rc,mid+1,R);
			T[node] = T[lc] + T[rc];
		}
	}
	int query(int pos,int node,int L,int R){
		assert(T[node] >= pos);
		if(L == R)return R;
		MID;CHILDEN;
		if(pos > T[lc])return query(pos-T[lc],rc,mid+1,R);
		else
			return query(pos,lc,L,mid);
	}
}tree;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    tree.build(1,1,n);
    int i = 0;
    for(int len = n; len > 1; --len){
    	int j = (i+m-1)%(len);

    	int ans = tree.query(j+1,1,1,n);
    	tree.update(ans,1,1,n);

    	printf("%d ",ans);
    	i = j%(len-1);
    }
    printf("%d
",tree.query(1,1,1,n));

    return 0;
}