Second My Problem First HDU - 3706 单调队列

单调队列

单调队列是指一个队列内部的元素具有严格单调性的一种数据结构，分为单调递增队列和单调递减队列。

单调队列满足两个性质

1.单调队列必须满足从队头到队尾的严格单调性。

2.排在队列前面的比排在队列后面的要先进队。

元素进队列的过程对于单调递增队列，对于一个元素a 如果 a > 队尾元素那么直接将a扔进队列如果 a <= 队尾元素则将队尾元素出队列知道满足 a 大于队尾元素即可；

单调栈和这个差不多。但是不管是那个它只有一端可以移动（比如单调队列你只能O(1)时间内获得队列头部元素，对于队列尾部就不一定了），这个时候你可以用stl的双端队列。或者你可以模拟队列嘛

题意：

S_i= Aⁱ%B

T_i= min{S_k} (i-A<=k<=i)

让你求所有T_i得乘积取模于B的得数

题解：

这就只需要维护一个长度为A（有可能还小于A）的单调队列就可以了

代码：

 1 #include <stdio.h>

 2 #include <string.h>

 3 #include <stdlib.h>

 4 #include <iostream>

 5 #include <algorithm>

 6 using namespace std;

 7 typedef long long ll;

 8 typedef unsigned long long ull;

 9 const int inf=0x3f3f3f3f;

10 const ll INF=0x3f3f3f3f3f3f3f3fll;

11 const int maxn=1e5+5;

12 int main()

13 {

14     ll n,a,b,s,e,que[maxn],sum,ans,pos[maxn];

15     while(~scanf("%lld%lld%lld",&n,&a,&b))

16     {

17         s=e=0;

18         ans=sum=1;

19         for(ll i=1;i<=n;++i)

20         {

21             ans=(ans*a)%b;

22             while(s<e && que[e-1]>ans) e--;

23             que[e]=ans;

24             pos[e++]=i;

25             if(s<e && pos[e-1]-pos[s]>a) s++;

26             sum=(sum*que[s])%b;

27         }

28         printf("%lld\n",sum);

29     }

30     return 0;

31 }

巴特西

Second My Problem First HDU - 3706 单调队列

最新文章

热门文章