HDU 3706——Second My Problem First

【タイトル説明】
Give you three integers n, A and B.  Then we define Si = Ai mod B and Ti = Min{ Sk | i-A <= k <= i, k >= 1} Your task is to calculate the product of Ti (1 <= i <= n) mod B.
【入力】
Each line will contain three integers n(1 <= n <= 107),A and B(1 <= A, B <= 231-1).  Process to end of file.
【出力】
For each case, output the answer in a single line.
【入力サンプル】
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
【出力サンプル】
2
3
4
5
6
【作者】
WhereIsHeroFrom@HDU
【出所】
HDOJ 5th Anniversary Contest
【アルゴリズム解析】
Siを計算し,次に［i−A,i］の中で最小のSiを取り出し,Tiに累乗し,最後にTi modBの値を出力した.
Siを計算して、私達は再帰的に計算することができて、しかしどのように[i-A,i]の中で最小のSiを探しますか?
直接列挙するのか?
いや!絶対TLE,10^7のデータ規模
では、どのように最適化しますか?
まず、10^7のループが必要であることを明確にします.どうして?Tiを累乗して計算するから
では、最適化の場所が明らかになったのは、最適化が[i-A,i]の中で、最小のSiをどのように探すかということです.
この検索区間を観察してみましょう:[i-A,i]何か見つかりましたか?
特徴:iの増加に伴い、この区間は移動ウィンドウのように右に1単位の長さを移動しました!!
では、つまり、ウィンドウを移動するたびに、ウィンドウの左側の要素が移動し、ウィンドウの右側の要素が新しく追加され、どのようなデータ構造が考えられますか?
キュー!
でもそれだけでいいの?私たちはどのようにこの特徴に基づいて最小の要素を探しますか?
キュー内の要素の単調性を保つことができます!!!
キュー内の単調性を維持するとは何ですか?
つまり、キューの要素は、単調に増加したり、単調に減少したりします!!しかし、この問題では、キュー内の要素が単調に増加することが要求されています.つまり、キューヘッダの要素はキュー全体の最小の要素であり、キューヘッダのidもキュー全体の最小の要素です.
では、問題が来ました.キューの要素を単調に増加させるにはどうすればいいですか.
普通のキューは1つのポートが入って、1つのポートが出て、それでは、どうして私たちは2つのポートが出て、1つのポートが入ってはいけませんか?
キューに要素を追加するたびに、この要素の前の要素が彼より大きいかどうかをチェックします.彼より大きいと、追加すると単調性全体が破壊されますか?
これはやりやすいですね.私たちは直接彼の前の要素を削除したら終わりではありません.もし削除した後もこのような状況であれば、彼の前の要素が彼より小さいまで削除し続けます.
ここでもう一つ問題がありますが、この要素を削除すると、[i-A,i]という区間の最小値を求めることに影響しますか?
なぜこの要素を削除したのか考えてみればわかるが、答えは否定的だ.
これがいわゆる単調なキューで、両端キューとも呼ばれます
この問題の実装コードを次に示します.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;
int main()
{
    int n,A,B;
    int q[100001],id[100001];
    while(scanf("%d%d%d",&n,&A,&B)!=EOF)
    {
        __int64 Ti=1,s=1;
        int head=0,tail=0;
        for(int i=1;i<=n;i++)
        {
            s=(s*A)%B;
            while(head<tail && q[tail]>=s) tail--;
            q[++tail]=s;
            id[tail]=i;
            while(id[head+1]<i-A) head++;
            Ti=(Ti*q[head+1])%B;
        }
        printf("%I64d
",Ti);
    }
    return 0;
}