题目链接: https://www.luogu.com.cn/problem/P1198

题意

现在请求你维护一个数列，要求执行M次以下两种操作：

1. 查询当前数列中末尾 L 个数中的最大的数，并输出这个数的值。
2. 将 n 加上t，其中 t 是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。

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

1≤M≤2e5, 1≤D≤2e9

思路

这题可以用线段树。但是一看题解发现居然可以用 ST表 ！这回明白了 ST表 的"离线"问询其实没有那么离线，至少还是可以在不修改元素的情况下增加数组的长度的。

这里用到的是逆向的ST表，通常我们的 dp[i][j] 维护的是 [a(i), a(i+2^j-1)] 的最值，当我们往后边增加新元素的时候，前面维护的最值会失效，如果要更新的话仅插入新元素的时间复杂度就是 O(nlogn)了，何况这里我们可能还有 M 次插入操作。

所以考虑把 dp[i][j] 所维护的值改成 [a(max(0, i-2^j+1)), a(i)] 的最值。此时每次插入新元素不会影响前面维护的最值。

复杂度 O(n·logn)。

代码

#include <iostream>
#include <cmath>
#include <algorithm>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 2e5+5;
int arr[maxN];
int mx[maxN][22];

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  int m, d; std::cin >> m >> d;
  int cnt = 0;
  int t = 0;
  orep(i, 0, m) {
    char c; int x; std::cin >> c >> x;
    if (c == 'A') {
      mx[cnt][0] = (x+t)%d;
      for (int j = 1; cnt-(1<<j)+1 >= 0; ++j) {
        mx[cnt][j] = std::max(mx[cnt][j-1], mx[cnt-(1<<(j-1))][j-1]);
      }
      ++cnt;
    } else {
      int k = log2(x);
      t = std::max(mx[cnt-1][k], mx[cnt-1-(x-(1<<k))][k]);
      std::cout << t; NL;
    }
  }

  return 0;
}