ural1521-线段树解约瑟夫问题

使用sum[]数组来记录当前区段的个数

pushup来更新子节点与父节点的关系，实现很简单，但是要注意每次节点个数在减少，注意查询时要求的长度要模一下当前节点的个数

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=100010;

int sum[maxn<<2];


void pushup(int  idx)
{
	sum[idx]=sum[idx<<1]+sum[idx<<1|1];
}

void build(int left,int right,int idx)
{
	sum[idx]=right-left+1;
	if(right==left)
		return ;
	int mid=(right+left)>>1;
	build(left,mid,idx<<1);
	build(mid+1,right,idx<<1|1);
}

int query(int val,int left,int right,int idx)
{
	if(right==left)
	{
		sum[idx]=0;
		return left;
	}
	int mid=(right+left)>>1;
	int ans;
	if(sum[idx<<1]>=val)
		ans=query(val,left,mid,idx<<1);
	else
		ans=query(val-sum[idx<<1],mid+1,right,idx<<1|1);
	pushup(idx);
	return ans;
}

int main()
{
	int N,K;

	scanf("%d%d",&N,&K);
	build(1,N,1);
	int temp=K;
	for(int i=1;i<=N;i++)
	{
		if(i!=N)
		printf("%d ",query(temp,1,N,1));
		else
			printf("%d",query(temp,1,N,1));
		if(i!=N)
			temp=(temp+K-1)%(N-i);
		if(temp==0)
			temp=N-i;
	}

}