YACS 2022年9月月赛 甲组 T1 游戏体验 题解

目前还没有时间写题解，疯狂复习$CSP$复赛中，这题是个线段树（自己可以探究一下，是动态的）

先贴个标程，需要的，请

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000005],x[1000005];
int ben[1000005],nxt[1000005],cur[1000005];
long long ans;
struct segment {
    int l, r;
    long long bst, lbst, rbst, sum;
} tr[4000005];
void add(int pos, int num) {
    tr[pos].bst = tr[pos].lbst = tr[pos].rbst = tr[pos].sum = num;
    for (int id = (pos >> 1); id; id >>= 1) {
        tr[id].sum = tr[2 * id].sum + tr[2 * id + 1].sum;
        tr[id].lbst = (tr[2 * id].lbst > tr[2 * id].sum + tr[2 * id + 1].lbst ? tr[2 * id].lbst : tr[2 * id].sum + tr[2 * id + 1].lbst);
        tr[id].rbst = (tr[2 * id + 1].rbst > tr[2 * id + 1].sum + tr[2 * id].rbst ? tr[2 * id + 1].rbst : tr[2 * id + 1].sum + tr[2 * id].rbst);
        long long s = (tr[2 * id].bst > tr[2 * id + 1].bst ? tr[2 * id].bst : tr[2 * id + 1].bst);
        tr[id].bst = (tr[2 * id].rbst + tr[2 * id + 1].lbst > s ? tr[2 * id].rbst + tr[2 * id + 1].lbst : s);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++i) cin >> x[i];
    tr[1].l = 1;
    tr[1].r = m;
    for (int i = 1; i <= 4000000; ++i) {
        if (tr[i].l != tr[i].r) tr[2 * i].l = tr[i].l, tr[2 * i].r = (tr[i].l + tr[i].r) / 2, tr[2 * i + 1].l = (tr[i].l + tr[i].r) / 2 + 1, tr[2 * i + 1].r = tr[i].r;
        else ben[tr[i].l] = i;
    }
    for (int i = m; i; --i) {
        nxt[i] = cur[x[i]];
        cur[x[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        if (cur[i]) {
            add(ben[cur[i]], a[i]);
            if (nxt[cur[i]]) add(ben[nxt[cur[i]]], -a[i]);
        }
    }
    for (int i = 1; i <= m; ++i) {
        ans = (ans > tr[1].bst ? ans : tr[1].bst);
        add(ben[i], 0);
        if (nxt[i]) add(ben[nxt[i]], a[x[i]]);
        if (nxt[nxt[i]]) add(ben[nxt[nxt[i]]], -a[x[i]]);
    }
    cout << ans << endl;
    return 0;
}