题目描述
现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。
输入格式
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。
输出格式
对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。
样例输入
5 100
A 96
Q 1
A 97
Q 1
Q 2
样例输出
96
93
96
Solution
这道题其实是可以用ST表过去的，因为每次更新的数都在最后面，所以就可以根据ST表的原理来做。
Code
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
| #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int D , m , n , d[200002] = {0} , dp[200002][30] , t = 0;
int max(int a , int b) {if (a > b) return a;else return b;}
void ch(int x) {
dp[x][0] = d[x];
for(int i = 1 ; x - (1 << i) >= 0 ; i++) dp[x][i] = max(dp[x][i - 1] , dp[x - (1 << (i - 1))][i - 1]);
}
int find(int ll , int rr) {
double u = log(rr - ll + 1) / log(2);
int k = u;
int maxi = max(dp[rr][k] , dp[ll + (1 << k) - 1][k]);
return maxi;
}
int main() {
memset(dp , 0 , sizeof(dp));
memset(d , 0 , sizeof(d));
scanf("%d%d" , & m , & D);
while(m--) {
int b = 0;
int f = 0;
char p;
cin >> p;
if (p == 'A') {
scanf("%d" , & b);
n++;
d[n] = (b + t) % D;
ch(n);
} else {
scanf("%d" , & f);
if (f == 1) {
printf("%d" , d[n]);
t = d[n];
} else {
t = find(n - f + 1 , n);
printf("%d" , t);
}
puts("");
}
}
return 0;
}
|
