描述
给定一列正整数 a1,a2,a3,…,an ，每一个数都在0 至 p–1 之间。可以对这列数进行两种操作： 添加操作：向序列后添加一个数，序列长度变成 n+1 。 询问操作：询问这个序列中最后 L 个数中最大的数是多少。 程序运行的最开始，整数序列为空。写一个程序，读入操作的序列，并输出询问操作的答案。
输入格式
输入文件maxnumber.in的第一行有两个正整数，m(1≤m≤200000)和 p(1≤p≤2∗109 )。 在接下来的 m 行中，每一行表示一个操作。如果该行的内容是Q l，则表示这个操作是询问序列中最后l个数的最大数是多少；如果是A t (0≤t<p) ，则表示向序列后面加一个数，加入的数是 (t+a) 除以 p 的余数。其中，t是输入的参数， a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则a=0）。 第一个操作一定是添加操作。对于询问操作， L>0 且不超过当前序列的长度。
输出格式
请将输出写入文件maxnumber.out。对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 L 个数的最大数。
测试样例
输入 10 100 A 97 Q 1 Q 1 A 17 Q 2 A 63 Q 1 Q 1 Q 3 A 99
输出 97 97 97 60 60 97
备注
最后的序列是97、14、60、96。
Solution： 求最后一段区间的最值，修改操作为添加在最后面。用单调栈即可在O(nlogn)内解决。
#include<stdio.h> #define M 200005 int A[M],Q[M],N=0; int main(){ int m,p,R=-1,last=0; scanf("%d %d",&m,&p); for(int i=1;i<=m;i++){ char str[5];int n; scanf("%s %d",str,&n); if(str[0]=='Q'){ int l=0,r=R,res; while(l<=r){ int mid=(l+r)>>1; if(Q[mid]>N-n){ r=mid-1; res=mid; }else l=mid+1; } printf("%d\n",A[Q[res]]); last=A[Q[res]]; }else{ A[++N]=(n+last)%p; while(R>=0&&A[Q[R]]<=A[N])R--; Q[++R]=N; } } return 0; }