提出 #72382755

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <functional>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define sz(x) (int)(x).size()
using namespace std;

template<typename Node>
struct SegTree {
    int n, lg, size;
    Node e; // 항등원
    vector<Node> tree;
    function<Node(Node, Node)> func;
    int log2(int n) {
        int res = 0;
        while (n > (1 << res)) res++;
        return res;
    }
    SegTree(int n, const Node& e, auto func) : n(n), lg(log2(n)), size(1<<lg), e(e), tree(size<<1, e), func(func) {}
    SegTree(const vector<Node>& v, const Node& e, auto func) : n(sz(v)), lg(log2(n)), size(1<<lg), e(e), tree(size<<1, e), func(func) {
        for (int i = 0; i < n; i++) {
            tree[i+size] = v[i];
        }
        for (int i = size-1; i > 0; i--) {
            tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
        }
    }
    void add(int i, const Node& val) {
        tree[--i |= size] += val;
        while (i >>= 1) {
            tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
        }
    }
    void update(int i, const Node& val) {
        tree[--i |= size] = val;
        while (i >>= 1) {
            tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
        }
    }
    Node query(int i) {
        return tree[--i | size];
    }
    Node query(int l, int r) {
        Node L = e, R = e;
        for (--l |= size, --r |= size; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) L = func(L, tree[l++]);
            if (~r & 1) R = func(tree[r--], R);
        }
        return func(L, R);
    }
    int find_kth(Node k) {
        int node = 1, st = 1, en = size;
        while (st != en) {
            int mid = (st + en) / 2;
            node <<= 1;
            if (tree[node] >= k) {
                en = mid;
            }
            else {
                k -= tree[node];
                node |= 1; st = mid+1;
            }
        }
        return st;
    }
};
typedef long long ll;
struct Node {
    int cnt, cnt2; ll sum;
    Node operator+(const Node& o) const {
        return { cnt + o.cnt, cnt2 + o.cnt2, sum + o.sum };
    }
    Node& operator+=(const Node& o) {
        cnt += o.cnt; cnt2 += o.cnt2;
        sum += o.sum; return *this;
    }
    bool operator>=(const Node& o) const {
        return cnt >= o.cnt;
    }
    Node& operator-=(const Node& o) {
        cnt -= o.cnt; return *this;
    }
};
const int MAX = 1e6;
int main() {
    fastio; int N, Q; cin >> N >> Q;
    SegTree<Node> sg(MAX, { 0, 0, 0 }, [](Node a, Node b) { return a + b; });
    ll sum2 = 0; int cnt2 = 0;
    vector<pair<ll,ll>> v(N);
    auto update = [&](ll a, int b, int ty) {
        int c2 = 0;
        if (b == 2) {
            cnt2 += ty; c2 = ty;
        }
        sum2 += ty * a;
        sg.add(a, { ty, c2, ty * a });
    };
    for (auto& [a, b] : v) {
        cin >> a >> b;
        update(a, b, 1);
    }
    auto calc = [&]() {
        int t = min(N-1, cnt2);
        if (t <= 0) {
            cout << sum2 << "\n"; return;
        }
        int idx = sg.find_kth({ sg.tree[1].cnt - t + 1, 0, 0 });
        auto up = sg.query(idx+1, MAX);
        int k = t - up.cnt;
        ll ans = sum2 + up.sum + (ll)k*idx;
        int c2 = up.cnt2;
        auto tmp = sg.query(idx);
        int b2 = max(0, k - tmp.cnt + tmp.cnt2);
        if (c2 + b2 == t && cnt2 == t) {
            ans -= idx;
            if (N > t) {
                int nxt = sg.find_kth({ sg.tree[1].cnt - t, 0, 0 });
                ans += nxt;
            }
        }
        cout << ans << "\n";
    };
    for (int q = 0; q < Q; q++) {
        int w, x, y; cin >> w >> x >> y;
        auto& [a, b] = v[w-1];
        update(a, b, -1);
        a = x; b = y;
        update(x, y, 1);
        calc();
    }
    return 0;
}

提出情報

ジャッジ結果