Submission #754799

#	Time	Username	Problem	Language	Result	Execution time	Memory
754799		Pring	Fire (JOI20_ho_t5)	C++14	100 / 100	478 ms	71428 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;

enum OP_TYPE {
    ADD,
    QUERY
};

struct Q {
    int t, l, r;
};

struct TRI {
    int x, y, val;
};

struct OP {
    OP_TYPE type;
    int t, id;
};

const int MXN = 200005;
int n, q, a[MXN], ans[MXN], lm[MXN], rm[MXN], opsz;
Q ask[MXN];
TRI tri[MXN * 4];
OP op[MXN * 5];

struct BIT {
    int val[MXN * 2], head, n;
    void init(int _n) {
        head = _n;
        n = 2 * _n;
    }
    void modify(int pos, int _val) {
        for (; pos <= n; pos += (pos & (-pos))) val[pos] += _val;
    }
    void modify_EX(int pos, int _val) {
        int pos0 = pos;
        for (; pos <= n; pos += (pos & (-pos))) val[pos] += _val * pos0;
    }
    int query(int pos) {
        int ans = 0;
        for (; pos > 0; pos -= (pos & (-pos))) ans += val[pos];
        return ans;
    }
    int rquery(int l, int r) {
        return query(r) - query(l - 1);
    }
} B[6];

struct DS1 {
    BIT *normal;
    void modify(int pos, int _val) {
        normal -> modify(normal -> head + pos, _val);
    }
    int query(int pos) {
        return normal -> query(normal -> head + pos);
    }
} ds1, ds2;

// struct DS2 {
//     BIT *normal;
//     void modify(int pos, int _val) {
//         normal -> modify(normal -> head + pos, _val);
//     }
//     int query(int pos) {
//         return normal -> query(normal -> head + pos);
//     }
// } ds2;

struct DS3 {
    BIT *normal, *special;
    void modify(int pos, int _val) {
        normal -> modify(normal -> head + pos, _val);
        special -> modify_EX(normal -> head + pos, _val);
    }
    int query(int pos) {
        return special -> rquery(special -> head + 1, special -> head + pos) - special -> head * normal -> rquery(normal -> head + 1, normal -> head + pos);
    }
} ds3, ds4;

// struct DS4 {
//     BIT *normal, *special;
//     void modify(int pos, int _val) {
//         normal -> modify(normal -> head + pos, _val);
//         special -> modify_EX(normal -> head + pos, _val);
//     }
//     int query(int pos) {
//         return special -> rquery(special -> head + 1, special -> head + pos) - special -> head * normal -> rquery(normal -> head + 1, normal -> head + pos);
//     }
// } ds4;

void MAKE_PLO() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() && a[st.top()] <= a[i]) {
            rm[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (st.size()) {
        rm[st.top()] = n + 1;
        st.pop();
    }
    for (int i = n; i > 0; i--) {
        while (st.size() && a[st.top()] < a[i]) {
            lm[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (st.size()) {
        lm[st.top()] = 0;
        st.pop();
    }
    // for (int i = 1; i <= n; i++) cout << lm[i] << ' ';
    // cout << endl;
    // for (int i = 1; i <= n; i++) cout << rm[i] << ' ';
    // cout << endl;
    int h, w;
    for (int i = 1; i <= n; i++) {
        if (lm[i] == 0) h = n;
        else h = i - lm[i];
        w = rm[i] - i;
        tri[4 * i - 4] = {i, 0, a[i]};
        tri[4 * i - 3] = {i, h, -a[i]};
        tri[4 * i - 2] = {i + w, w, -a[i]};
        tri[4 * i - 1] = {i + w, h + w, a[i]};
    }
    // for (int i = 0; i < 4 * n; i++) cout << '<' << tri[i].x << ' ' << tri[i].y << ' ' << tri[i].val << '>' << endl;
}

void MAKE_OP() {
    for (int i = 0; i < 4 * n; i++) {
        op[i] = {ADD, tri[i].y, i};
    }
    for (int i = 4 * n; i < 4 * n + q; i++) {
        op[i] = {QUERY, ask[i - 4 * n].t, i - 4 * n};
    }
    sort(op, op + 4 * n + q, [](OP a, OP b) {
        if (a.t != b.t) return a.t < b.t;
        if (a.type != b.type) return a.type == ADD;
        return a.id < b.id;
    });
    opsz = 4 * n + q;
}

void INIT_SMG() {
    for (int i = 0; i < 6; i++) B[i].init(n);
    ds1.normal = &B[0];
    ds2.normal = &B[1];
    ds3.normal = &B[2];
    ds3.special = &B[3];
    ds4.normal = &B[4];
    ds4.special = &B[5];
}

void NEXT() {
    // cout << "NEXT" << endl;
    B[1].head--;
    B[4].head--;
    B[5].head--;
}

void ADD_TRI(int id) {
    TRI &tg = tri[id];
    // cout << "ADD_TRI ";
    // cout << '<' << tg.x << ' ' << tg.y << ' ' << tg.val << '>' << endl;
    ds1.modify(tg.x, tg.val);
    ds2.modify(tg.x + 1, -tg.val);
    ds3.modify(tg.x, tg.val);
    ds4.modify(tg.x + 1, -tg.val);
}

int PRECALC(int pos) {
    // cout << ds1.query(pos) << ' ' << ds2.query(pos) << ' ' << ds3.query(pos) << ' ' << ds4.query(pos) << endl;
    return (pos + 1) * (ds1.query(pos) + ds2.query(pos)) - (ds3.query(pos) + ds4.query(pos));
}

int GETANS(int id) {
    Q &tg = ask[id];
    // cout << "GETANS ";
    // cout << '<' << tg.t << ' ' << tg.l << ' ' << tg.r << '>' << endl;
    return PRECALC(tg.r) - PRECALC(tg.l - 1);
    // return 0;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < q; i++) {
        cin >> ask[i].t >> ask[i].l >> ask[i].r;
        if (ask[i].t >= n) ask[i].t = n - 1;
    }
    MAKE_PLO();
    MAKE_OP();
    INIT_SMG();
    for (int i = 0; i < opsz; i++) {
        if (op[i].t == n) break;
        // if (i && op[i].t > op[i - 1].t) NEXT();
        for (int j = op[i - 1].t; j < op[i].t; j++) NEXT();
        if (op[i].type == ADD) ADD_TRI(op[i].id);
        else ans[op[i].id] = GETANS(op[i].id);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
    return 0;
}

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