題目： Josephus問題的定義如下：假設n個人排成環形，且有以正整數m<=n。從某個制定的人開始，沿環報數，每遇到第m個人就讓其出列，且報數進行下去。這個過程一直進行到所有人都出列為止。每個人出列的次序定義了整數1，2，...，n的(n, m)-Josephus排列。例如，(7,3)-Josephus排列為<3,6,2,7,5,1,4>。 a)假設m為整數。請描述一個O(n)時間的算法，使之對給定的整數n，輸出(n, m)-Josephus排列。 b)假設m不是個常數。請描述一個O(nlgn)時間的算法，使給定的整數n和m，輸出(n, m)-Josephus排列。 思考： 利用14.1中的動態順序統計，假設剛剛刪除的是剩余點中的第start個點（初始時為0），此時還剩下t個點，那么下一個要刪除的是剩余點的第（start+m-1）%t個點 步驟1：基礎數據結構 紅黑樹 步驟2：附加信息 size[x]：以x為根的子樹的（內部）結點數（包括x本身），即子樹的大小。size[nil[T]]=0 步驟3：對信息的維護 size[x] = size[left[x]] + size[right[x]] + 1 插入操作：從插入結點到根結點都要更新O(lgn) 旋轉操作：只需要更新旋轉軸上的兩個點O(1) 刪除操作：從刪除結點的父結點開始到根結點都要更新O(lgn) 代碼： https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/exercise14_2.cpp