現在請求你維護一個數列，要求提供以下兩種操作： 1、 查詢操作。語法：Q L 功能：查詢當前數列中末尾L個數中的最大的數，並輸出這個數的值。限制：L不超過當前數列的長度。 2、 插入操作。語法：A n 功能：將n加上t，其中t是最近一次查詢操作的答案（如果還未執行過查詢操作，則t=0)，並將所得結果對一個固定的常數D取模，將所得答案插入到數列的末尾。限制：n是非負整數並且在長整范圍內。注意：初始時數列是空的，沒有一個數。
第一行兩個整數，M和D，其中M表示操作的個數(M <= 200,000)，D如上文中所述，滿足(0
對於每一個查詢操作，你應該按照順序依次輸出結果，每個結果占一行。
5 100
A 96
Q 1
A 97
Q 1
Q 2
96
93
96
看到本題，首先想到線段樹。線段樹寫了一半發現， 插入操作 完成不了。所以轉化思路，維護數組完成插入，查找的數據結構有哪些呢？Splay？SBT？這些雖說可以很快地解決此題，但是面對一百多行的模板依倍感壓力。。。。。所以在這裡介紹一個特殊的數據結構------單調隊列。這種數據結構不太常用，但是對於這種題還是可以飛速解決的。單調隊列，顧名思義，就是一個隊列中的關鍵元素，按照某種方式排列。例如單調遞增或單調遞減。這裡的單調隊列是一個單調遞減的隊列，接下來就是單調隊列的使用方法。
首先單調隊列一定是單調的，此題中因為查找的是後l位的最大值，所以我們設一個隊列名為maxx[]。maxx[i]表示從i到數列結尾的最大值。查找末尾L位的最大值時，輸出maxx[len-L+1]即可。len為數列的長度。好了，隊列完成了，然後就是該怎麼更新隊列的值了------
我們假定一個數列 1 2 3 4 5 這個數列不管詢問末尾幾位的最大值均是 5 那麼在maxx數組中就可以這樣存：5 5 5 5 5 全填上 5 就好了這樣不管L是幾，我們在輸出maxx[len-L+1]時都不會影響。再比如這個數列 1 2 5 4 3 這樣在單調對列中的存儲方式為 5 5 5 4 3。假如詢問後一位的最大值時返回值是 3 ，末兩位的返回值是 4。末3、4、5位均是5。可以發現一個規律，在插入元素時，只要這個元素比隊尾的元素小則加入隊尾，比隊尾元素大則替換之，直到找到比該元素小的為止，這就是單調隊列的精華所在！！
貼下代碼：（有一些要注意的在代碼中體現）
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=2001000;
long long int a[MAXN],maxx[MAXN];//long long的原因是在不斷累加的過程中可能會超出整形的范圍
int last=0,M,mod,len;// 我可是有親身經歷的
int main()
{
scanf("%d%d",&M,&mod);
for(int t=1;t<=M;t++){
char c;
int x;
scanf("%s%d",&c,&x);
if(c=='A'){
a[++len]=(last+x)%mod;
for(int i=len;i>=1;i--)//因為是單調遞減，所以從最後一位開始比較
if(maxx[i]<a[len]) maxx[i]=a[len];//若隊列中的值比插入值小則替換
else break;//若比插入值大則停止，因為越靠近隊首值越大，無須比較
}
else{
printf("%d\n",maxx[len-x+1]);//直接輸出即可
last=maxx[len-x+1];
}
}
}
可以轉載，請注明來源！！！
