题目大意

维护一个数列，有以下两种操作：

1. 查询当前数列中末尾$L$个数中的最大的数

2. 将$A_n$加上$t$，其中$t$是最近一次查询操作的答案（如果还未执行过查询操作，则$t=0$)，并将所得结果对一个固定的常数$D$取模，将所得答案插入到数列的末尾。

初始时数列是空的，且$n$为$0$

数据范围

$m\leqslant 200000$

题解

开好最大范围的线段树，初始为空

插入操作，确定好插入的位置

查询操作，查询线段树$[cnt-l+1,cnt]$最大值(其中$cnt$为当前已经插进线段树的数值个数)

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
using namespace std;

int t[800500];
int m,mod,cnt,last,x;

void insert(int p,int nowl,int nowr,int x,int c){
    if (nowl==nowr) {t[p]=c;return;}
    int mid=(nowl+nowr)>>1;
    if (x<=mid) insert(p<<1,nowl,mid,x,c);
    else insert(p<<1|1,mid+1,nowr,x,c);
    t[p]=max(t[p<<1],t[p<<1|1]);
}
int findmx(int p,int nowl,int nowr,int l,int r){
    if ((nowl==l)&&(nowr==r)) return t[p];
    int mid=(nowl+nowr)>>1;
    if (r<=mid) return findmx(p<<1,nowl,mid,l,r);
    else if (l>mid) return findmx(p<<1|1,mid+1,nowr,l,r);
    else return max(findmx(p<<1,nowl,mid,l,mid),findmx(p<<1|1,mid+1,nowr,mid+1,r));
}

int main(){
    memset(t,-inf,sizeof(t));
    scanf("%d%d",&m,&mod);
    For(i,1,m){
        char ch[10];scanf("%s",ch+1);
        if (ch[1]=='A'){
            cnt++;
            scanf("%d",&x);x=(x+last)%mod;
            insert(1,1,m,cnt,x);
        }
        else{
            scanf("%d",&x);
            last=findmx(1,1,m,cnt-x+1,cnt);
            printf("%d\n",last);
        }
    }
    return 0;
}