ジョセフス問題2(1168号)

白俊-ジョセフス問題2(1168号)
この問題では、Nのサイズが増加し、時間制限が減少する.
すなわち,上記の解法のように,ベクトルをEraseで解きながら解くことでは解決できない.
これは,時間的複雑度をO(n 2)O(n^2)O(n^2)O(n^2)O(n 2)O(n 2)O(n 2)O(n 2)O(n 2)O(n 2)の時間的複雑度に低減することを意味する.
ジョセフス問題の核心は、必要なインデックスの数字を取得するときに、削除した数字をスキップしなければならないことです.
たとえば、0から始まる配列は次のようになります.
Vector : 1 2 3 4
このとき2番目の数字3を消し、2番目の数字を消したら4を消します.
すなわち、配列を参照してn番目の数字を削除すると、消去された数字はカウントできない.
ここで考えられる資料構造はSegment Treeである.
Segment Treeは、特定区間の情報を管理する際に有用な資料構造である.
この問題では、Segment Treeは、以下に示すように、セグメント内のアクティブな要素の数を管理するために使用されます.

この状態で、3番目と6番目を削除する手順は次のとおりです.

実装では、左側ノードを削除する場合と右側ノードを削除する場合、Indexを表示する方法が異なることに注意してください.
例えば、最初の写真では、5の場合はルートから右側のノードに流れ、これは1〜4の後の最初のインデックスを意味する.
そのため、右に流れるときは5を使用しないで、右に流れると最初のインデックスが見つかります.
左に曲がるとツリーを直接使用してインデックスを検索でき、右に曲がるとSubtreeのインデックスを再取得すべきだと考えられます.(コードindex - segment[node * 2]部)
コードは以下の通りです.

#include <iostream>

using namespace std;

int n, k;

int segment[300000];

int init(int start, int end, int node)
{
	if (start == end) 
		return segment[node] = 1;
	
	int mid = (start + end) / 2;
	return segment[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

int get_num_and_update(int start, int end, int node, int index)
{
	segment[node]--;
	if (start == end) 
		return start;
	
	int mid = (start + end) / 2;
	if (index > segment[node * 2]) 
		return get_num_and_update(mid + 1, end, node * 2 + 1, index - segment[node * 2]);
	else 
		return get_num_and_update(start, mid, node * 2, index);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	init(1, n, 1);
	int idx = k - 1;
	cout << "<";
	for (int i = 1; i <= n; i++) {
		int get_idx = get_num_and_update(1, n, 1, idx + 1);
		
		if (i != n) 
			cout << get_idx << ", ";
		else 
			cout << get_idx;

		if (segment[1] == 0)
			break;

		idx += k - 1;
		idx %= segment[1];
	}
	cout << ">";
	return 0;
}