非常裸的线段树  ||

单调队列：

假设一个节点在队列中既没有时间优势（早点入队）也没有值优势（值更大），那么显然不管在如何的情况下都不会被选为最大值。

   既然它仅仅在末尾选。那么自然能够满足以上的条件。

线段树

#include "stdio.h"#include "string.h" struct node{    int l,r,Max;}data[800010];  int Max(int a,int b){    if (a
     
      mid) return query(l,r,k*2+1);    else return Max(query(l,mid,k*2),query(mid+1,r,k*2+1));} int main(){    int m,d,t,x,now;    char ch[2];    while (scanf("%d%d",&m,&d)!=EOF)    {        build(1,m,1);        t=0;        now=0;        while (m--)        {            scanf("%s%d",ch,&x);            if (ch[0]=='A')            {                x=(x+t)%d;                now++;                updata(now,1,x);             }else            {                t=query(now-x+1,now,1);                printf("%d\n",t);            }        }    }    return 0;}
     

单调队列：

#include "stdio.h"#include "string.h"int f[200010];int main(){    int t,now,m,d,x,i;    char ch[2];    while (scanf("%d%d",&m,&d)!=EOF)    {        t=0;        now=0;        while (m--)        {            scanf("%s%d",ch,&x);            if (ch[0]=='A')            {                f[++now]=(x+t)%d;                for (i=now-1;i>=1;i--)                if (f[i]