1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

void solve() {
    int n;
    cin >> n;
    vl a(2 * n);
    rep(i, 0, 2 * n - 1) cin >> a[i];
    int idx = -1, idx2 = -1;
    rep(i, 0, 2 * n - 1) {
        if (a[i] == 0) {
            if (idx == -1)
                idx = i;
            else
                idx2 = i;
        }
    }
    int l = idx + 1, r = idx2 - 1;
    bool flag = true;
    while (l <= r) {
        if (a[l] != a[r]) {
            flag = false;
            break;
        }
        l++, r--;
    }
    map<int, int> ma;
    l = idx - 1, r = idx2 + 1;
    while (l >= 0 && r <= 2 * n - 1) {
        if (a[l] == a[r]) {
            ma[a[l]]++;
            l--, r++;
        } else
            break;
    }
    rep(i, idx, idx2) { ma[a[i]]++; }
    int ans = 0;
    if (flag) {
        while (ma.count(ans)) ans++;
    }
    int ans2 = 0;
    ma.clear();
    l = idx, r = idx;
    while (l >= 0 && r <= 2 * n - 1) {
        if (a[l] == a[r]) {
            ma[a[l]]++;
            l--, r++;
        } else
            break;
    }
    while (ma.count(ans2)) ans2++;
    ma.clear();
    int ans3 = 0;
    l = idx2, r = idx2;
    while (l >= 0 && r <= 2 * n - 1) {
        if (a[l] == a[r]) {
            ma[a[l]]++;
            l--, r++;
        } else
            break;
    }
    while (ma.count(ans3)) ans3++;
    cout << max({ans, ans2, ans3}) << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    ll tem = 0;
    rep(i, 0, n - 1) tem += a[i];
    vl suf(n + 1, INT_MAX);
    frep(i, n - 1, 0) suf[i] = min(suf[i + 1], a[i]);
    rep(i, 0, n - 1) ans += 1LL * suf[i];
    ll ans2 = ans;
    map<ll, ll> ma;
    rep(i, 0, n - 1) {
        if (ma.count(a[i])) ans2 = min(ans2, ans - ma[a[i]]);
        ma[suf[i]]++;
    }
    cout << tem - min(ans, ans2) << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

template <typename T = long long>
class Tree {
    vector<T> tree;

public:
    // 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
    Tree(int n, T val = 0) : tree(n + 1) {
        for (int i = 1; i <= n; i++) {
            tree[i] += val;
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
    Tree(const vector<T>& data) {
        int n = data.size();
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            tree[i] += data[i - 1];  // data是 0-based
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 单点修改：将 0-based 下标 i 处的元素增加 val
    void add(int i, T val = 1) {
        for (++i; i < tree.size(); i += i & (-i)) {
            tree[i] += val;
        }
    }

    // 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
    T pre(int i) const {
        T res = 0;
        for (++i; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);  // 当 l=0 时, pre(-1) 会合理地返回 0
    }

    // 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
    int lower_bound(T val) const {
        int w = bit_width(tree.size() - 1);
        int res = 0;
        T s = 0;
        for (int i = w - 1; i >= 0; i--) {
            int nxt = res + (1 << i);
            if (nxt < tree.size() && tree[nxt] + s < val) {
                res += (1 << i);
                s += tree[nxt];
            }
        }
        return res;  // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
    }
};
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll maxx = *max_element(all(a));
    Tree<ll> tree(maxx + 1);
    Tree<ll> tree2(maxx + 1);
    ll ans = 0;
    ll tem = 0;
    rep(i, 0, n - 1) {
        ll tem2 = tree2.query(a[i] + 1, maxx);
        ll tem3 = tree.query(a[i] + 1, maxx);
        ans += tem3 - tem2 * a[i];
        tree.add(a[i], a[i]);
        tree2.add(a[i], 1);
    }
    ll ans2 = ans;
    Tree<ll> tree3(maxx + 1);
    Tree<ll> tree4(maxx + 1);
    rep(i, 0, n - 1) { tree4.add(a[i], 1); }
    rep(i, 0, n - 1) {
        ll tem2 = tree3.query(a[i], maxx);
        ll tem3 = tree4.query(0, a[i] - 1);
        ans2 = max(ans2, ans + tem2 - tem3);
        tree3.add(a[i], 1);
        tree4.add(a[i], -1);
    }
    cout << max(ans, ans2) << endl;
    return;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

template <typename T = long long>
class Tree {
    vector<T> tree;

public:
    // 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
    Tree(int n, T val = 0) : tree(n + 1) {
        for (int i = 1; i <= n; i++) {
            tree[i] += val;
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
    Tree(const vector<T>& data) {
        int n = data.size();
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            tree[i] += data[i - 1];  // data是 0-based
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 单点修改：将 0-based 下标 i 处的元素增加 val
    void add(int i, T val = 1) {
        for (++i; i < tree.size(); i += i & (-i)) {
            tree[i] += val;
        }
    }

    // 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
    T pre(int i) const {
        T res = 0;
        for (++i; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);  // 当 l=0 时, pre(-1) 会合理地返回 0
    }

    // 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
    int lower_bound(T val) const {
        int w = bit_width(tree.size() - 1);
        int res = 0;
        T s = 0;
        for (int i = w - 1; i >= 0; i--) {
            int nxt = res + (1 << i);
            if (nxt < tree.size() && tree[nxt] + s < val) {
                res += (1 << i);
                s += tree[nxt];
            }
        }
        return res;  // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
    }
};
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl pre(n);
    pre[0] = a[0];
    rep(i, 1, n - 1) {
        if (i % 2 == 1)
            pre[i] = pre[i - 1] - a[i];
        else
            pre[i] = pre[i - 1] + a[i];
    }
    vl tem;
    for (ll& p : pre) tem.push_back(p);
    tem.push_back(0);
    auto sorted = tem;
    ranges::sort(sorted);
    sorted.erase(unique(all(sorted)), sorted.end());
    int m = sz(sorted);
    Tree<ll> tree(m);
    Tree<ll> tree2(m);
    int tem2 = ranges::lower_bound(sorted, 0) - sorted.begin();
    tree.add(tem2, 1);
    ll ans = 0;
    rep(i, 0, n - 1) {
        if (i % 2 == 0) {
            int tem2 = ranges::lower_bound(sorted, pre[i]) - sorted.begin();
            ll tem3 = tree.query(0, tem2 - 1);
            ans += tem3;
            tree2.add(tem2, 1);
        } else {
            int tem2 = ranges::lower_bound(sorted, pre[i]) - sorted.begin();
            ll tem3 = tree2.query(tem2 + 1, m - 1);
            ans += tem3;
            tree.add(tem2, 1);
        }
    }
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

void solve() {
    int n, x, y;
    cin >> n;
    vvi ma(n);
    vi deg(n);
    rep(i, 1, n - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    int tem = 0;
    vector<bool> vis(n, false);
    rep(i, 0, n - 1) {
        if (sz(ma[i]) == 1) vis[i] = true;
        tem += vis[i];
    }
    vi cnt(n);
    vi dep(n);
    vi tem2(n);
    vi tem3(n);
    ll ans = 0;
    int idx = -1;
    rep(i, 0, n - 1) {
        if (!vis[i]) {
            idx = i;
            break;
        }
    }
    auto dfs = [&](this auto&& dfs, int x, int pa, int d) -> int {
        dep[x] = d;
        if (vis[x]) {
            tem2[x] = 1;
            ans++;
            return 1;
        }
        int tem3 = 0;
        for (int& p : ma[x]) {
            if (p == pa) continue;
            int tem4 = dfs(p, x, d + 1);
            tem3 += tem4;
        }
        tem2[x] = tem3;
        if (x != idx && tem2[x] % 2 == 1) ans++;
        return tem3;
    };
    dfs(idx, -1, 0);
    if (tem % 2 == 0) {
        cout << ans << endl;
        return;
    }
    auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> void {
        if (x != idx) tem3[x] = tem3[pa] + tem2[x] % 2;
        for (int& p : ma[x]) {
            if (p == pa) continue;
            dfs2(p, x);
        }
    };
    dfs2(idx, -1);
    ll ans2 = LLONG_MAX;
    rep(i, 0, n - 1) {
        if (vis[i]) ans2 = min(ans2, ans + dep[i] - 2 * tem3[i]);
    }
    cout << ans2 << endl;
    return;
}