結果

問題 No.1526 Sum of Mex 2
ユーザー Rheo TommyRheo Tommy
提出日時 2021-04-29 22:19:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 280 ms / 3,000 ms
コード長 7,121 bytes
コンパイル時間 3,081 ms
コンパイル使用メモリ 226,140 KB
実行使用メモリ 29,824 KB
最終ジャッジ日時 2024-11-08 21:23:03
合計ジャッジ時間 8,876 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 26 ms
6,912 KB
testcase_14 AC 40 ms
9,344 KB
testcase_15 AC 44 ms
9,728 KB
testcase_16 AC 234 ms
29,184 KB
testcase_17 AC 169 ms
27,008 KB
testcase_18 AC 19 ms
6,400 KB
testcase_19 AC 13 ms
5,248 KB
testcase_20 AC 91 ms
15,872 KB
testcase_21 AC 189 ms
28,928 KB
testcase_22 AC 114 ms
17,024 KB
testcase_23 AC 203 ms
29,184 KB
testcase_24 AC 210 ms
29,568 KB
testcase_25 AC 227 ms
29,184 KB
testcase_26 AC 228 ms
29,440 KB
testcase_27 AC 236 ms
29,440 KB
testcase_28 AC 254 ms
29,696 KB
testcase_29 AC 240 ms
29,440 KB
testcase_30 AC 249 ms
29,824 KB
testcase_31 AC 232 ms
29,824 KB
testcase_32 AC 244 ms
29,312 KB
testcase_33 AC 280 ms
29,336 KB
evil_largest AC 980 ms
99,728 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (int) n; i++)

using lint = long long;
const lint LINF = 1ll << 60;

class SegTreeBeats {
    unsigned int n;
    std::vector<lint> width, min[2], minc, max[2], maxc, sum, lazy;
    
    void eval(int k) {
        if (n - 1 <= k)return;
        if (lazy[k]) {
            update_node_add(2 * k + 1, lazy[k]);
            update_node_add(2 * k + 2, lazy[k]);
            lazy[k] = 0;
        }
        if (max[0][k] < max[0][2 * k + 1]) {
            update_node_max(2 * k + 1, max[0][k]);
        }
        if (min[0][k] > min[0][2 * k + 1]) {
            update_node_min(2 * k + 1, min[0][k]);
        }
        if (max[0][k] < max[0][2 * k + 2]) {
            update_node_max(2 * k + 2, max[0][k]);
        }
        if (min[0][k] > min[0][2 * k + 2]) {
            update_node_min(2 * k + 2, min[0][k]);
        }
    }
    
    void combine(int k) {
        sum[k] = sum[2 * k + 1] + sum[2 * k + 2];
        if (min[0][2 * k + 1] < min[0][2 * k + 2]) {
            min[0][k] = min[0][2 * k + 1];
            minc[k] = minc[2 * k + 1];
            min[1][k] = std::min(min[1][2 * k + 1], min[0][2 * k + 2]);
        } else if (min[0][2 * k + 1] > min[0][2 * k + 2]) {
            min[0][k] = min[0][2 * k + 2];
            minc[k] = minc[2 * k + 2];
            min[1][k] = std::min(min[0][2 * k + 1], min[1][2 * k + 2]);
        } else {
            min[0][k] = min[0][2 * k + 1];
            minc[k] = minc[2 * k + 1] + minc[2 * k + 2];
            min[1][k] = std::min(min[1][2 * k + 1], min[1][2 * k + 2]);
        }
        if (max[0][2 * k + 1] > max[0][2 * k + 2]) {
            max[0][k] = max[0][2 * k + 1];
            maxc[k] = maxc[2 * k + 1];
            max[1][k] = std::max(max[1][2 * k + 1], max[0][2 * k + 2]);
        } else if (max[0][2 * k + 1] < max[0][2 * k + 2]) {
            max[0][k] = max[0][2 * k + 2];
            maxc[k] = maxc[2 * k + 2];
            max[1][k] = std::max(max[0][2 * k + 1], max[1][2 * k + 2]);
        } else {
            max[0][k] = max[0][2 * k + 1];
            maxc[k] = maxc[2 * k + 1] + maxc[2 * k + 2];
            max[1][k] = std::max(max[1][2 * k + 1], max[1][2 * k + 2]);
        }
    }
    
    void update_node_max(int k, lint x) {
        sum[k] += (x - max[0][k]) * maxc[k];
        if (max[0][k] == min[0][k])min[0][k] = x;
        else if (max[0][k] == min[1][k])min[1][k] = x;
        max[0][k] = x;
    }
    
    void update_node_min(int k, lint x) {
        sum[k] += (x - min[0][k]) * minc[k];
        if (min[0][k] == max[0][k])max[0][k] = x;
        else if (min[0][k] == max[1][k])max[1][k] = x;
        min[0][k] = x;
    }
    
    void update_node_add(int k, lint x) {
        min[0][k] += x;
        if (min[1][k] != LINF)min[1][k] += x;
        max[0][k] += x;
        if (max[1][k] != -LINF)max[1][k] += x;
        sum[k] += x * width[k];
        lazy[k] += x;
    }

public:
    SegTreeBeats(unsigned int size, lint def = 0) {
        *this = SegTreeBeats(std::vector<lint>(size, def));
    }
    
    SegTreeBeats(std::vector<lint> initvec) {
        n = 1;
        while (n < initvec.size())n *= 2;
        width.resize(2 * n - 1);
        min[0].resize(2 * n - 1);
        min[1].resize(2 * n - 1, LINF);
        minc.resize(2 * n - 1);
        max[0].resize(2 * n - 1);
        max[1].resize(2 * n - 1, -LINF);
        maxc.resize(2 * n - 1);
        sum.resize(2 * n - 1);
        lazy.resize(2 * n - 1);
        for (int i = n - 1; i < n - 1 + initvec.size(); i++) {
            min[0][i] = max[0][i] = sum[i] = initvec[i - n + 1];
            minc[i] = maxc[i] = 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            combine(i);
        }
        width[0] = n;
        REP(i, 2 * n - 2) width[i] = width[(i - 1) / 2] / 2;
    }
    
    void update_chmin(int a, int b, lint x, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (b <= l || r <= a || max[0][k] <= x)return;
        if (a <= l && r <= b && max[1][k] < x) {
            update_node_max(k, x);
            return;
        }
        eval(k);
        update_chmin(a, b, x, 2 * k + 1, l, (l + r) / 2);
        update_chmin(a, b, x, 2 * k + 2, (l + r) / 2, r);
        combine(k);
    }
    
    void update_chmax(int a, int b, lint x, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (b <= l || r <= a || x <= min[0][k])return;
        if (a <= l && r <= b && x < min[1][k]) {
            update_node_min(k, x);
            return;
        }
        eval(k);
        update_chmax(a, b, x, 2 * k + 1, l, (l + r) / 2);
        update_chmax(a, b, x, 2 * k + 2, (l + r) / 2, r);
        combine(k);
    }
    
    void update_add(int a, int b, lint x, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (b <= l || r <= a)return;
        if (a <= l && r <= b) {
            update_node_add(k, x);
            return;
        }
        eval(k);
        update_add(a, b, x, 2 * k + 1, l, (l + r) / 2);
        update_add(a, b, x, 2 * k + 2, (l + r) / 2, r);
        combine(k);
    }
    
    void update(int a, int b, lint x) {
        update_chmin(a, b, x);
        update_chmax(a, b, x);
    }
    
    lint query_sum(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (b <= l || r <= a)return 0;
        if (a <= l && r <= b)return sum[k];
        eval(k);
        lint vl = query_sum(a, b, 2 * k + 1, l, (l + r) / 2);
        lint vr = query_sum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }
    
    lint query_min(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (b <= l || r <= a)return LINF;
        if (a <= l && r <= b)return min[0][k];
        eval(k);
        lint vl = query_min(a, b, 2 * k + 1, l, (l + r) / 2);
        lint vr = query_min(a, b, 2 * k + 2, (l + r) / 2, r);
        return std::min(vl, vr);
    }
    
    lint query_max(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (b <= l || r <= a)return -LINF;
        if (a <= l && r <= b)return max[0][k];
        eval(k);
        lint vl = query_max(a, b, 2 * k + 1, l, (l + r) / 2);
        lint vr = query_max(a, b, 2 * k + 2, (l + r) / 2, r);
        return std::max(vl, vr);
    }
};

int main() {
    lint n;
    std::cin >> n;
    std::vector<lint> v(n);
    REP(i, n) std::cin >> v[i];
    
    std::vector<std::vector<lint>> h(n + 1, std::vector<lint>(1, n));
    h[0].push_back(0);
    REP(i, n) {
        h[v[i]].push_back(i);
    }
    REP(i, n + 1) {
        std::sort(h[i].begin(), h[i].end());
        std::reverse(h[i].begin(), h[i].end());
    }
    
    lint ans = 0;
    SegTreeBeats st(n + 1);
    REP(i, n + 1) {
        lint p = h[i].back();
        h[i].pop_back();
        st.update_chmax(i, n + 2, p);
    }
    
    REP(i, n) {
        ans += n * (n + 1) - st.query_sum(0, n + 2);
        lint vi = v[i];
        lint next = h[vi].back();
        h[vi].pop_back();
        st.update_chmax(vi, n + 2, next);
        st.update_chmax(0, n + 2, i + 1);
    }
    
    std::cout << ans << std::endl;
}
0