用平衡树求解约瑟夫问题

题目大意

 $n\ $个人编号为$\ 1\ $到$\ n$，按照编号围成一圈。从$\ 1\ $号开始，按照循序依次数数，第一次跳过$\ a_1\ $个人后停止，停止时指向的下一个人出局，然后继续数数，第二次跳过的人数为$\ a_2$，以此类推，直到所有人出局为止。

给定$\ a_1,a_2,...,a_n$，请依次输出出局人员的编号。

数据范围

• 对于$\ 30\%\ $的数据，$\ n\leq 1000$
• 对于$\ 60\%\ $的数据，$\ n\leq 50000$
• 对于$\ 100\%\ $的数据，$\ 1\leq n\leq 500,000$，$0\leq a_i< n$

算法思路

自从掌握FHQ Treap之后，发现好多题目都可以用它来做。像这道题目简直就是平衡树裸题。会写平衡时直接就AC。

除去平衡树代码，main函数代码非常简练。

int main(){
    int n,pos=1;
    n = read();
    build(n); //笛卡尔建树 O(n)
    //for(int i=1;i<=n;i++) insert(i,i); //O(nlogn) 
    while(fhq[root].size){
        pos += read();   
        pos = (pos - 1) % fhq[root].size + 1; //O(1) 计算位置 
        write(remove(pos));//O(logn) 删除 
        putchar('\n');
    }
    return 0;
}

约瑟夫扩展问题

• 支持在线进行报不同数字
• 支持在线交换两个人的位置
• 甚至支持区间内人编号翻转