线段树解约瑟夫环

题干：

这道题如果用循环链表模拟，时间复杂度很不友好，O(mn)，绝对超时。听大佬们说可以用线段树来做，用线段树来查询下一次要删除的数，时间复杂度最终为O(nlogn)。

网上看了这个大佬关于线段树的详解：https://blog.csdn.net/zearot/article/details/48299459

最终AC代码：

#include <bits/stdc++.h>
using namespace std;

struct node{
    int num;
    int l;
    int r;
};

node *tree;

void build(int left,int right,int index)
{
    tree[index].l=left;
    tree[index].r=right;

    if(right==left){
        tree[index].num=1;
        return;
    }

    int mid=(left+right)/2;

    build(left,mid,index<<1);//构建左子树
    build(mid+1,right,index<<1|1);//构建右子树

    tree[index].num=tree[index<<1].num+tree[index<<1|1].num;
}

int update(int p,int index)
{
    if(tree[index].r==tree[index].l){
        tree[index].num=0;
        return tree[index].r;
    }
    tree[index].num--;

    if(p<=tree[index<<1].num)//如果p<=左子节点中有效元素的个数则从左叶子节点删除
        return update(p,index<<1);
    else//否则从右子节点中删除
        return update(p-tree[index<<1].num,index<<1|1);
}
int main()
{
    int n,m,k;
    while(cin>>n>>m>>k){
        tree=new node[3*n];
        build(1,n,1);//构建范围是从[1,n]的线段树
        int seq=k;
        for(int i=0;i<n;i++){
            seq=(seq+m-1)%tree[1].num;
            if(seq==0)
                seq=tree[1].num;
            cout<<update(seq,1)<<" ";
        }
        cout<<endl;
    }
}