Title Link: https://www.luogu.com.cn/problem/P1198

Title:

Title Description

Now you are requested to maintain a sequence. The following two operations are required:

1. Query operation.

Syntax: Q L

Function: query the maximum number of the last L numbers in the current sequence, and output the value of this number.

Limit: l does not exceed the length of the current sequence. (L > 0)

2. Insert operation.

Syntax: A n

Function: add n to t, where tt is the answer of the latest query operation (t = 0 if the query operation has not been performed), take the modulus of a fixed constant D for the obtained result, and insert the obtained answer to the end of the sequence.

Limit: n is an integer (possibly negative) and is in the long integer range.

Note: the initial time sequence is empty and there is no number.

Input format

The first line consists of two integers, M ， and D ， where M ， represents the number of operations, D ， as described above.

The next M} lines, each with a string, describe a specific operation. The syntax is as described above.

Output format

For each query operation, you should output the results in order, and each result occupies one row.

Input and output samples

Enter #1 copy

5 100
A 96
Q 1
A 97
Q 1
Q 2

Output #1 copy

96
93
96

Description / tips

Data scale and agreement

For all test points, ensure 1 < = m < = 2e5, 1 < = d < = 2E9.

Analysis:

1. Dynamically modify the number at a certain position

2. Find the maximum value of an interval

Both can be operated using a segment tree.

So what values should be maintained in the segment tree?

Generally, segment trees are stored in the form of structures.

An L, an R, and then maintain the attributes, or some auxiliary attributes.

Whether to store auxiliary attributes depends on whether the attributes we currently need can be obtained through the attributes of two child nodes. If we can, we don't need to store auxiliary attributes. If we can't, we need to store some auxiliary attributes.

This problem can directly record the maximum value of the interval. From the maximum value of the child node, we get the maximum value we need.

At the same time, this problem only needs to use one of the important operations of the segment tree, the push () operation, to obtain the attribute value of the parent node through the child node.

At the same time, this problem can preprocess the segment tree with length m. Then, the value of the corresponding interval in the corresponding segment tree is modified by single point modification. Then used for query.

Code implementation:

# include <iostream>
using namespace std;

const int M = 2e5 + 10;

struct edg
{
    int l,r;  // Maintain the left and right endpoints of this interval
    int v; // Maintenance maximum
}edgs[4 * M]; // Generally, it is 4 times the interval length

int m,d;

int pushup(int u) // Segment tree is one of the most important operations Calculate the information to be maintained by the parent node from the child node information
{
    edgs[u].v = max(edgs[2 * u].v , edgs[2 * u + 1].v);
}

void build(int u , int l , int r) // Create a segment tree. U is the current node, u is the root node, l is the left endpoint, and r is the right endpoint
{
    edgs[u].l = l;
    edgs[u].r = r;
    if(l == r) // Leaf node, you can assign the left and right children of the leaf node to themselves, and then return directly
    {
        return;
    }
    int mid = (l + r) / 2;
    build(u * 2 , l , mid); // Left subtree
    build(u * 2 + 1 ,mid +1 , r); // Note that the right subtree is mid + 1 ~ r
}

int query(int u , int l , int r) //Find the maximum value of l~r interval
{
    if(edgs[u].l >= l && edgs[u].r <= r) // That is, the current interval is the interior of the desired interval
    {
        return edgs[u].v; // Direct return value
    }
    int mid = ( edgs[u].l + edgs[u].r ) / 2;
    int v = 0;
    if(l <= mid) // You need to traverse the left subtree
    {
        v = query(u * 2 , l , r);
    }
    if(r > mid) // R needs to be > mid, not equal to. When we create it, the intervals of the left and right subtrees are: l,mid; mid + 1, r
    {
        v = max(query(u * 2 + 1 , l , r) , v);
    }
    return v;
}

void modify(int u , int x , int v) // The value of a node in an interval changes
{
    if(edgs[u].l == x && edgs[u].r == x)
    {
        edgs[u].v = v;
    }
    else
    {
        int mid = (edgs[u].l + edgs[u].r) / 2;
        if(x <= mid)
        {
            modify(u * 2 , x , v);
        }
        else
        {
            modify(u *2 + 1 , x , v);
        }
        pushup(u); //If the child node changes, the parent node is updated by the child node,
    }
}

int main()
{
    int n = 0;
    int last = 0;
    scanf("%d %d",&m,&d);
    build(1,1,m);
    while(m--)
    {
        string ch;
        int t;
        cin >> ch >>t;
        if(ch == "A")
        {
            int temp = (last + t) % d;
            modify(1,n + 1,temp);
            n++;
        }
        else
        {
            last = query(1,n - t + 1,n);
            printf("%d\n",last);
        }
    }
    return 0;
}