單調隊列1001 HDU 3706 Second My Problem First 單調隊列入門題

Problem Description

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.

題意:

給n個數,第i個數是A^i%B,求sigma(T[i])

T[i]=min(Val[j])|j>=1&&j<=i&&j>=i-A

思路:

維護一個單調隊列的入門題

單調隊列是一個同時維護頭指針和尾指針的雙端隊列

假設我們維護一個單調遞減的單調隊列

必須保證越靠近頭指針越小

如果此時我們插入一個數x,我們從尾指針到頭指針周遊

直到隊列為空或者有個數小于x,如果周遊的時候不滿足前邊的條件

那麼把這個隊列裡的元素扔出隊列

由于我們每個元素隻入出隊列各一次,是以總是時間複雜度是O(n)的

而且單調隊列中,入隊時間永遠是隊頭>=隊尾

神奇的資料結構…ORZ

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = ;
const int inf=(<<)-;
deque<pair<LL,int> >Que;
int main()
{
    int n,A,mod; 
    while(~scanf("%d%d%d",&n,&A,&mod))
    {
        Que.clear();
        LL tmp=,ans=;
        for(int i=;i<=n;++i)
        {
            tmp=(tmp*A)%mod;
            while(Que.empty()==  && tmp<=Que.back().first)
            Que.pop_back();
            Que.push_back(make_pair(tmp,i));
            while(Que.empty()==  &&i-Que.front().second>A)
            Que.pop_front();
            ans=(ans*Que.front().first)%mod;
        }
        printf("%lld\n",ans);
    }
    return ;
}