hdu3706基础的单调队列

题意：
解释题意不如直接把这个题粘贴过来，因为题目很短题意很容易懂。
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.
 
Input
Each line will contain three integers n(1 <= n <= 107),A and B(1 <= A, B <= 231-1). 
Process to end of file.
 
Output
For each case, output the answer in a single line.

Sample Input

1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
 
Sample Output
2
3
4
5
6


思路：
      比较简单的一个单调队列题目，我们可以建立一个单调递增的单调队列，开一个1000W的数组，不用怕报内存，内存够，然后我们每次都把一个新值进队列，然后把队尾比这个值大于等于的出队，对头把下标之差大于A的出队就行了，每次都是把一个新的值放进队列，然后在对头拿一个最小的来作为当前的T,然后一边更新，一边拿，一边记录答案就行了，O(n)的时间复杂度，1000W的，可以过（不过感觉还是有点险，但这个题目都O(n)了在过不了，那估计就设计到转换什么的了，那我就做不了了，嘿嘿）。

#include<stdio.h>

#include<string.h>


#define N 10000005


typedef struct

{

int id;

__int64 num;

}NODE;


NODE Q[N];

int tou ,wei;

__int64 A ,B ,n;


void insert(int id ,__int64 num)

{

for(int i = wei ;i > tou ;i --)

{

if(Q[wei].num >= num) wei --;

else break;

}

Q[++wei].num = num;

Q[wei].id = id;

for(int i = tou + 1 ;i <= wei ;i ++)

if(id - Q[i].id > A) tou ++;

else break;

}


int main ()

{

while(~scanf("%d %I64d %I64d" ,&n ,&A ,&B))

{

__int64 now = A % B;

__int64 Ans = 1;

tou = wei = 0;

for(int i = 1 ;i <= n ;i ++)

{

insert(i ,now);

Ans = (Ans * Q[tou+1].num) % B;

now = now * A % B;

}

printf("%I64d\n" ,Ans);

}

return 0;

}