Josephus Problem-セグメントツリー検索

自分の学習過程を記録するだけです
Josephus Problem-セグメントツリー検索

タイトル説明

私の簡単な分析

詳細コード

補足説明

タイトルの説明
タイトルは?There are n people standing in a circle waiting to be executed. The counting out begins at the first people in the circle and proceeds around the circle in the counterclockwise direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.
In traditional Josephus Problem, the number of people skipped in each round is fixed, so it’s easy to find the people executed in the i-th round. However, in this problem, the number of people skipped in each round is generated by a pseudorandom number generator:
x[i+1] = (x[i] * A + B) % M.
Can you still find the people executed in the i-th round?
入力
The first line of each test cases contains six integers 2 ≤ n ≤ 100000, 0 ≤ m ≤ 100000, 0 ≤ x[1], A, B < M ≤ 100000. The second line contains m integers 1 ≤ q[i] < n.
出力For each test case,output a line containing m integers,the people executed in the q[i]-th round.
サンプル入力2 1 0 1 2 3 1 41 5 1 0 2 2 2 3 40
サンプル出力1 2 4 6 8 35
私の簡単な分析
この問題を書く前にもう3つのJosephusの問題を書いたことがあります.問題を出した指導教師は3つの問題をそれぞれ過程シミュレーション、F(2 n)とF(n)の関係を探し、大問題化小問題の3つの方法で書いたと言っていますが、私の3つの問題はすべて大問題化校の問題を書いて、つまり再帰式で解きましたが、時間が限られているのでアルゴリズムをいくつか最適化しました.不要なプロセスをスキップしました.私は同じ方法でこの問題を書いて、公式を変えて、毎回スキップした人数を更新するつもりだったが、考えてみると拒否した.
以下は私の个人的な考えです:もし単纯に公式の再帰で书くならば、先にタイムアウトするかどうかを考えないで、求めなければならないのは1ラウンドごとに輪を出す人の番号なので、1ラウンドごとに后で輪を出す人がいて、単纯に公式の再帰で輪を出す人が缲り返して、甚だしきに至っては后の结果も间违いがあります.
公式で再帰することはできますが、各ラウンドの後に輪を出た人を取り除く必要があります.そうすれば、彼は後の過程に影響を与えません.最後にCSDNで他のブロガーのブログで線分樹を見たので、簡単に線分樹を勉強して、線分樹でこのテーマを作ると考えがスムーズになりました.まず私のコードを貼って、それから私はもう少し補足説明をします.他のブロガーの考えを参考にしているので、コードが同じになるかもしれません.私個人の勉強だけです.
線分ツリーについてこのブログリンクをお勧めします.
詳細コード

#include 
#include 
#include 
#include 
using namespace std;
 
 
//       
long long T[1000007];
 
 
//       
void  tree(long long l, long long r, long long n)
{
    long long m;
 
    T[n] = r - l + 1;
    m = (l + r) / 2;
 
    //      0   
    if (l == r)
        return;
 
    tree(l, m, n * 2);
    tree(m + 1, r, n * 2 + 1);
}
 
 
 
//           
long long newT(long long l, long long r, long long n, long long change)
{
    long long m;
    T[n]--;
 
    ////      0   
    if (l == r)
        return l;
 
    //                      ，       
    m = (l + r) / 2;
    if (change <= T[2 * n])
        return newT(l, m, n * 2, change);
 
    else
        return newT(m + 1, r, n * 2 + 1, change - T[2 * n]);
 
}
 
 
 
int main()
{
    long long n, m, x, a, b, M, s;
    long long q[100007] = { 0 };         //         
    long long num[100007] = { 0 };         //         
    while (cin >> n)
    {
        cin >> m >> x >> a >> b >> M;
 
        s = 1;
        
        //     
        tree(1, n, 1);
 
        //       
        for (long long i = 1; i <= n; i++)
        {
            s = (s + x) % T[1];
 
            // s  0，s  （s+x）， T[1]；
            if (s == 0)
            {
                s = T[1];
            }
 
            num[i] = newT(1, n, 1, s);
            x = ((x * a)%M + b) % M;
        }
 
 
        //    
        for (long long i = 1; i <= m; i++)
        {
            cin >> q[i];
        }
 
 
        //             
        for (long long i = 1; i <= m; i++)
        {
            cout << num[q[i]] << " ";
        }
 
        cout << endl;
 
    }
}

補足説明
私が一般的に見ているセグメントツリーは、左端点と右端点をそれぞれ格納していますが、ここでは各セグメントの長さを格納し、端点の値は転送されるパラメータごとに格納されています.1ラウンドごとに1人が退輪するので、退輪する人がいる部分の長さを1つ減らして探している間に、1ラウンドごとに1人が退輪するので、本来は出輪する必要がある人は前のラウンドにスキップした人を加えて1を加え、ここにスキップした人を加えるだけです.
同級生と話していたとき、線分樹を更新するときに右のchangeに戻ってT[n 2]を減らさなくてもいいかと聞かれましたが、身につけていないので、後で一緒に検討してみましたが、実はこれをT[n 2]減らして、左の動きが減った人です.
この問題は実質的に現在の残りの輪の中の第change個人の番号を探すので、左側は一人を減算するごとに、右側で検索するときは元の上に前に位置を付ける必要があります.右側のchange値に戻りたい場合は、木を建てるときに右端の値を保存し、輪を出るたびに、この人がいる線分の値を1減らす必要があるほか、この人がいる線分が右の線分に対応する値も1を減らす必要があり、このような変化は複雑で、意味がない.
私の理解は比較的に浅くて、甚だしきに至っては自分の考えに対する強引な解釈で、もし私の間違いを発見したら、評論区で指摘してほしいです.ありがとうございます.