제출 #1326711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326711		ivan_alexeev	Fire (JOI20_ho_t5)	C++20	100 / 100	613 ms	93832 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif

using ll = long long;
const ll inf = 1'000'000'000'000'000'000;

const int N = 200'010;

struct node{
    int cnt;
    ll sum;
    ll ans;
};

node merge(node a, node b){
    node ans;
    ans.cnt = a.cnt + b.cnt;
    ans.sum = a.sum + b.sum;
    ans.ans = a.ans + b.ans + a.sum * b.cnt;
    return ans;
}

struct segtree{
    node d[4 * N];
    void build(int u = 0, int l = 0, int r = N){
        d[u] = {r - l, 0, 0};
        if(l + 1 != r){
            int m = (l + r) / 2;
            build(u * 2 + 1, l, m);
            build(u * 2 + 2, m, r);
        }
    }
    int ql, qr, ind;
    ll dd;
    node gg(int u, int l, int r){
        if((ql >= r) || (qr <= l)){
            return {0, 0, 0};
        }
        if((ql <= l) && (r <= qr)){
            return d[u];
        }
        int m = (l + r) / 2;
        return merge(gg(u * 2 + 1, l, m), gg(u * 2 + 2, m, r));
    }
    void uu(int u, int l, int r){
        if(l + 1 == r){
            d[u].sum += dd;
            d[u].ans += dd;
        }else{
            int m = (l + r) / 2;
            if(ind < m){
                uu(u * 2 + 1, l, m);
            }else{
                uu(u * 2 + 2, m, r);
            }
            d[u] = merge(d[u * 2 + 1], d[u * 2 + 2]);
        }
    }
    ll get(int ql1, int qr1){
        ql = ql1;
        qr = qr1;
        auto ans = gg(0, 0, N);
        ql = 0;
        qr = ql1;
        return ans.ans + gg(0, 0, N).sum * ans.cnt;
    }
    void update(int ind1, ll dd1){
        ind = ind1;
        dd = dd1;
        uu(0, 0, N);
    }
};

struct running_segtree{
    node d[8 * N];
    void build(int u = 0, int l = 0, int r = 2 * N){
        d[u] = {r - l, 0, 0};
        if(l + 1 != r){
            int m = (l + r) / 2;
            build(u * 2 + 1, l, m);
            build(u * 2 + 2, m, r);
        }
    }
    int ql, qr, ind;
    ll dd;
    node gg(int u, int l, int r){
        if((ql >= r) || (qr <= l)){
            return {0, 0, 0};
        }
        if((ql <= l) && (r <= qr)){
            return d[u];
        }
        int m = (l + r) / 2;
        return merge(gg(u * 2 + 1, l, m), gg(u * 2 + 2, m, r));
    }
    void uu(int u, int l, int r){
        if(l + 1 == r){
            d[u].sum += dd;
            d[u].ans += dd;
        }else{
            int m = (l + r) / 2;
            if(ind < m){
                uu(u * 2 + 1, l, m);
            }else{
                uu(u * 2 + 2, m, r);
            }
            d[u] = merge(d[u * 2 + 1], d[u * 2 + 2]);
        }
    }
    int shift = N;
    void step(){
        shift--;
    }
    ll get(int ql1, int qr1){
        ql = ql1 + shift;
        qr = qr1 + shift;
        auto ans = gg(0, 0, 2 * N);
        ql = 0;
        qr = ql1 + shift;
        return ans.ans + gg(0, 0, 2 * N).sum * ans.cnt;
    }
    void update(int ind1, ll dd1){
        ind = ind1 + shift;
        dd = dd1;
        uu(0, 0, 2 * N);
    }
};

segtree st;
running_segtree st1;

struct query{
    int l;
    int r;
    int ind;
};

ll get(int l, int r){
    return st.get(l, r) + st1.get(l, r);
}

void solve(){
    st.build();
    st1.build();
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<vector<query>> qq(n + 1);
    for(int i = 0; i < q; i++){
        int l, r, t;
        cin >> t >> l >> r;
        l--;
        qq[t].push_back({l, r, i});
    }
    vector<vector<pair<int, ll>>> events(n + 2), events1(n + 2);
    vector<int> left(n), right(n);
    deque<pair<ll, int>> z = {{inf, - n - 2}};
    for(int i = 0; i < n; i++){
        while(z.back().first <= a[i]){
            z.pop_back();
        }
        left[i] = z.back().second;
        z.push_back({a[i], i});
    }
    z = {{inf, n}};
    for(int i = n - 1; i >= 0; i--){
        while(z.back().first < a[i]){
            z.pop_back();
        }
        right[i] = z.back().second;
        z.push_back({a[i], i});
    }
    for(int i = 0; i < n; i++){
        int l = left[i], r = right[i];

        events[0].emplace_back(i, a[i]);
        events[min(i - l - 1, n + 1)].emplace_back(i, -a[i]);
        events[r - i - 1].emplace_back(r, -a[i]);
        events[min(r - l - 1, n + 1)].emplace_back(r, a[i]);

        events1[0].emplace_back(i + 1, -a[i]);
        events1[r - i - 1].emplace_back(r, a[i]);
        events1[min(i - l - 1, n + 1)].emplace_back(i, a[i]);
        events1[min(r - l - 1, n + 1)].emplace_back(r, -a[i]);

    }
    vector<ll> ans(q);
    for(int i = 0; i <= n; i++){
        // cout << "xxxxxxxxxxxxxxxxxxxxxxx " << i << endl;
        for(auto [ind, dd] : events[i]){
            st.update(ind, dd);
        }
        for(auto [ind, dd] : events1[i]){
            st1.update(ind, dd);
        }
        // st.vivo();
        // st1.vivo();
        // cout << endl;
        for(auto [l, r, ind] : qq[i]){
            // cout << "aaaa " << l << ' ' << r << ' ' << ind << endl;
            // cout << st.get(l, r) << ' ' << st1.get(l, r) << endl;
            ans[ind] = get(l, r);
        }
        st1.step();
    }
    for(auto i : ans){
        cout << i << endl;
    }
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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