题目大意

维护一个序列,支持两种操作。A x:向序列尾部插入数x,Q x:询问序列尾部后x个元素的最大值

解题思路

啊,题目这么水,随意写个线段树或树状数组维护就好啦。

代码

#include <bits/stdc++.h>

#define L(a) (a<<1)
#define R(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)

using namespace std;
static int M, D, N, r;

struct Ques{
    char opt;
    int n;
}q[200005];

struct Node{
    int Left;
    int Right;
    int Max;
}s[800005];

void Input()
{
    scanf("%d%d", &M, &D);
    for(int i=1; i<=M; i++)
    {
        getchar();
        scanf("%c%d", &q[i].opt, &q[i].n);
        if(q[i].opt == 'A') N++;
    }
}

void Build(int p,int l,int r)
{
    s[p].Left = l; s[p].Right = r;
    s[p].Max = 0;
    if(l == r) return;
    int mid = MID(l,r);
    Build(L(p),l,mid);
    Build(R(p),mid+1,r);
}

void Add(int p,int x,int key)
{
    if(s[p].Left == s[p].Right) {
        s[p].Max = key;
        return;
    }
    int mid = MID(s[p].Left, s[p].Right);
    if(x <= mid) Add(L(p), x, key);
    else Add(R(p), x, key);
    s[p].Max = max(s[L(p)].Max, s[R(p)].Max);
}

int Query(int p,int l,int r)
{
    if(s[p].Left==l && s[p].Right==r) return s[p].Max;
    int mid = MID(s[p].Left, s[p].Right);
    if(r <= mid) return Query(L(p), l, r);
    else if(l > mid) return Query(R(p), l, r);
    else return max(Query(L(p), l, mid), Query(R(p), mid+1, r));
}

int main()
{
    Input();
    Build(1,1,N);
    int t = 0;
    r = 0;
    for(int i=1; i<=M; i++) {
        if(q[i].opt == 'A') {
            q[i].n = (q[i].n + t) % D;
            Add(1, ++r, q[i].n);
        }
        else if(q[i].opt == 'Q') {
            t = Query(1, r-q[i].n+1, r);
            printf("%d\n",t);
        }
    }
    return 0;
}