算法

树状数组

因为每次询问的区间是最后几个数字，而树状数组可以快速求前缀，所以不妨倒着存储数据。

为了减少时间复杂度，要提前预留m个坑位，第一个数存放到m，第二个数存放到m-1，以此类推。

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10;
int tr[N],m,p,j;
int lowbit(int x)
{
    return x&(-x);
}
void add(int n,int x)
{
    for(int i=n;i<=m;i+=lowbit(i)) tr[i]=max(tr[i],x);
}
int quary(int n)
{
    int res=0;
    for(int i=n;i;i-=lowbit(i)) res=max(res,tr[i]);
    return res;
}
int main()
{
    cin>>m>>p;
    int last=0;
    j=m;
    for(int i=0;i<m;i++)
    {
        int x;
        char c[2];
        scanf("%s%d",c,&x);
        if(*c=='A')
            add(j--,((long long)x+last)%p);
        else
        {
            last=quary(j+x);
            printf("%d\n",last);
        }
    }
}