Submission #254966

#	Time	Username	Problem	Language	Result	Execution time	Memory
254966		imeimi2000	Fire (JOI20_ho_t5)	C++17	100 / 100	643 ms	47176 KiB

ho_t5

#include <bits/stdc++.h>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

struct fenwick {
    static const int N = 200005;
    llong fen[N + N + 5];
    void init() {
        memset(fen, 0, sizeof(fen));
    }
    void update(int i, llong x) {
        i += N;
        while (i <= N + N) {
            fen[i] += x;
            i += i & -i;
        }
    }
    llong query(int i) const {
        i += N;
        llong ret = 0;
        while (i) {
            ret += fen[i];
            i -= i & -i;
        }
        return ret;
    }
} fen1, fen2;

int n, q;
int S[200001];
pii seg[1 << 19];

void init(int i, int s, int e) {
    if (s == e) {
        seg[i] = pii(S[s], s);
        return;
    }
    int m = (s + e) / 2;
    init(i + i, s, m);
    init(i + i + 1, m + 1, e);
    seg[i] = max(seg[i + i], seg[i + i + 1]);
}

pii query(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return pii(0, 0);
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return max(query(i + i, s, m, x, y), query(i + i + 1, m + 1, e, x, y));
}

vector<pair<pii, int>> U;
void solve(int s, int e) {
    if (s > e) return;
    int m = query(1, 1, n, s, e).se;
    if (s > 1) {
        U.emplace_back(pii(m, m - s + 1), -S[m]);
        U.emplace_back(pii(e + 1, e - s + 2), S[m]);
    }
    {
        U.emplace_back(pii(m, 0), S[m]);
        U.emplace_back(pii(e + 1, e - m + 1), -S[m]);
    }
    solve(s, m - 1);
    solve(m + 1, e);
}

llong ans[200001];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> S[i];
    init(1, 1, n);
    solve(1, n);
    vector<pair<pii, int>> Q;
    for (int i = 1; i <= q; ++i) {
        int t, l, r;
        cin >> t >> l >> r;
        Q.emplace_back(pii(r, t), i);
        Q.emplace_back(pii(l - 1, t), -i);
    }
    for (int it = 0; it < 2; ++it) {
        sort(U.begin(), U.end());
        sort(Q.begin(), Q.end());
        fen1.init();
        fen2.init();
        for (int i = 0, j = 0; i < int(Q.size()); ++i) {
            while (j < int(U.size()) && U[j].fs.fs <= Q[i].fs.fs) {
                int jx = U[j].fs.se - U[j].fs.fs;
                fen1.update(jx, U[j].se);
                fen2.update(jx, U[j].se * (1ll - U[j].fs.fs));
                ++j;
            }
            int ix = Q[i].fs.se - Q[i].fs.fs - it;
            llong val = fen1.query(ix) * Q[i].fs.fs + fen2.query(ix);
            if (Q[i].se < 0) ans[-Q[i].se] -= val;
            else ans[Q[i].se] += val;
        }
        for (auto &i : U) swap(i.fs.fs, i.fs.se);
        for (auto &i : Q) swap(i.fs.fs, i.fs.se);
    }
    for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80