「Bzoj 1012」「JSOI2008」最大数maxnumber (线段树 / 树状数组)

BZOJ 1012
树状数组解法：
$c[i]$维护$[i-\operatorname{lowbit}(i)+1,i]$的最大值，$a[i]$为原数组

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL m, D, x, cnt, lastans = 0;
    LL a[200000 + 5], c[200000 + 5]; // c[i]维护[i-lowbit(i)+1,i]的最大值，a[i]为原数组
    char s[5];

    LL lowbit(LL x) {return x & (-x);}
    LL query(LL l, LL r) {
        LL ret = a[r];
        while (l <= r) {
            ret = max(ret, a[r]);
            for (--r; r - l >= lowbit(r); r -= lowbit(r)) 
                ret = max(ret, c[r]);
        }
        return ret;
    }

    void clean() {
        cnt = 0, ms(a, 0), ms(c, 0);
    }
    int solve() {

        clean();
        cin >> m >> D;
        for (LL i = 1; i <= m; ++i) {
            scanf("%s%lld", s, &x);
            if (s[0] == 'A') {
                a[++cnt] = (x + lastans) % D;
                c[cnt] = max(a[cnt], query(cnt - lowbit(cnt) + 1, cnt));
            } else {
                printf("%lld\n", lastans = query(cnt - x + 1, cnt));
            }
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

线段树解法：
线段树维护区间最大值单点修改即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)

namespace flyinthesky {  

    const LL MAXN = 200000 + 5;

    LL now, n, d;
    LL maxv[MAXN * 4];
    char s[4];

    void pushup(LL o) {maxv[o] = max(maxv[lc], maxv[rc]);}
    void build(LL o, LL l, LL r) {
        maxv[o] = 0;
        if (l == r) return ; else build(lc, l, M), build(rc, M + 1, r);
        pushup(o);
    }
    LL query(LL o, LL l, LL r, LL x, LL y) {
        if (x <= l && r <= y) return maxv[o];
        LL ans = 0;
        if (x <= M) ans = max(ans, query(lc, l, M, x, y));
        if (M < y) ans = max(ans, query(rc, M + 1, r, x, y));
        return ans;
    }
    void update(LL o, LL l, LL r, LL p, LL v) {
        if (l == r) {maxv[o] = v; return ;}
        if (p <= M) update(lc, l, M, p, v); else if (M < p) update(rc, M + 1, r, p, v);
        pushup(o);
    } 

    void clean() {
        now = 0;
    }
    int solve() {
        scanf("%lld%lld", &n, &d);
        clean();
        build(1, 1, n);
        LL t = 0;
        for (LL x, i = 1; i <= n; i++) {
            scanf("%s%lld", s, &x);
            if (s[0] == 'A') update(1, 1, n, ++now, (x + t) % d); 
            else printf("%lld\n", t = query(1, 1, n, now - x + 1, now));
        }
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}