数据结构作业——最大数

发表于 分类于 阅读次数：

最大数
时间限制: 1000 ms
内存限制: 128 MB

现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。(L > 0)
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t = 0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入格式：
第一行两个整数，M和D，其中MM表示操作的个数(M ≤ 200,000)，D如上文中所述，满足(0 < D < 2,000,000,000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。

输出格式：
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入样例:

1
2
3
4
5
6
5 100
A 96
Q 1
A 97
Q 1
Q 2

输出样例:

1
2
3
96
93
96

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>

struct node
{
    int val, pos;
} stack[200005];

int cnt = 0, top = -1;

void push(int val)    //压栈，维护单调递减
{
    while(top >= 0 && stack[top].val <= val)
        top--;
    stack[++top].val = val;
    stack[top].pos = cnt++;
}

int query(int len)    //二分查找
{
    int ans, mid, l = 0, r = top;
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(stack[mid].pos >= cnt - len)
        {
            r = mid - 1;
            ans = stack[mid].val;
        }
        else
            l = mid + 1;
    }
    return ans;
}

int main()
{
    int m, d, t = 0;
    long long val;
    char cmd[2];
    scanf("%d%d", &m, &d);
    while(m--)
    {
        scanf("%s%lld", cmd, &val);
        if(cmd[0] == 'A')
            push((val + t) % d);
        else
            printf("%d\n", t = query(val));
    }
    return 0;
}