表面上是一道线段树的裸题,但实际上用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;
}
Last modification:February 22nd, 2020 at 12:05 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏