表面上是一道线段树的裸题,但实际上用ST表就可以很好的解决。
ST表是一个静态数据结构,不支持在线修改,但是我们可以发现对于本题而言,在末尾插入一个数并不会影响先前的信息,所以我们采用ST表的方法来完成本题。
值得注意的是,在维护ST表的时候,我们需要注意方向。
参考代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200001;
ll m, d, t;
ll Max[N][21];
ll a[N];
int len;
ll Query(int l, int r) {
int k = log2(r - l + 1);
return max(Max[l + (1 << k) - 1][k], Max[r][k]);
}
void Add(int x) {
Max[x][0] = a[x];
for ( int i = 1; x - (1 << i) >= 0; ++i )
Max[x][i] = max(Max[x][i - 1], Max[x - (1 << (i - 1))][i - 1]);
}
int main() {
scanf("%lld%lld", &m, &d);
char op;
ll opn;
for ( int i = 1; i <= m; ++i ) {
cin >> op >> opn;
if ( op == 'Q' )
printf("%lld\n", t = Query(len - opn + 1, len));
else {
a[++len] = (opn + t) % d;
Add(len);
}
}
return 0;
}