#1190682 (C++23) No.3772 Discrete Addition

• 問題: No.3772 Discrete Addition
• ユーザー: apricity
• 提出日時: 2026-09-28 15:45:55
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,050 ms / 8,000 ms
• コード長: 10,450 bytes
• コンパイル時間: 1,714 ms
• コンパイル使用メモリ: 198,944 KB
• 実行使用メモリ: 48,696 KB
• 最終ジャッジ日時: 2026-10-16 20:56:15
• 合計ジャッジ時間: 6,957 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 12

ソースコード

#include <array>
#include <cstdint>
#include <string>
#include <cassert>
#include <iostream>
#include <system_error>
#include <tuple>
#include <vector>
#include <algorithm>
#include <optional>

using namespace std;
using i64 = int64_t;
using i128 = __int128_t;

struct DynamicLowerHull {
    struct Point {
        i64 x = 0;
        i64 y = 0;
    };

    struct Lazy {
        i64 dx = 0;
        i64 a = 0;
        i128 b = 0;
    };

    struct Node {
        bool valid = false;
        Point lb{}, rb{};
        i64 min_x = 0;
    };

    int n, sz;
    vector<Node> dat;
    vector<Lazy> lazy;

    DynamicLowerHull(const vector<optional<Point>>& xs): n((int)xs.size()) {
        sz = 1;
        while (sz < n) sz <<= 1;
        dat.resize(2 * sz);
        lazy.resize(sz);
        for (int i = 0; i < n; ++i) if (xs[i]) dat[sz+i] = Node{true, *xs[i], *xs[i], xs[i]->x};
        for (int k = sz - 1; k > 0; --k) pull(k);
    }

    static i128 cross(const Point& a, const Point& b, const Point& c) {
        return (i128)(b.y - a.y) * (c.x - a.x) - (i128)(c.y - a.y) * (b.x - a.x);
    }

    static Lazy compose(const Lazy& f, const Lazy& g) {
        return { f.dx + g.dx, f.a + g.a, f.b + g.b + (i128)f.a * g.dx };
    }

    static Point mapping(Point p, const Lazy& f) {
        p.y += (i128)f.a * p.x + f.b;
        p.x += f.dx;
        return p;
    }

    void all_apply(int k, const Lazy& f) {
        if (!dat[k].valid) return;
        dat[k].lb = mapping(dat[k].lb, f);
        dat[k].rb = mapping(dat[k].rb, f);
        dat[k].min_x += f.dx;
        if (k < sz) lazy[k] = compose(f, lazy[k]);
    }

    void push(int k) {
        if (k >= sz) return;
        all_apply(2 * k, lazy[k]);
        all_apply(2 * k + 1, lazy[k]);
        lazy[k] = Lazy{};
    }

    void pull(int k) {
        int l = 2 * k;
        int r = l + 1;
        Node& s = dat[k];
        if (!dat[l].valid and !dat[r].valid) {
            s = Node{};
            return;
        }
        if (!dat[l].valid) {
            s = dat[r];
            return;
        }
        if (!dat[r].valid) {
            s = dat[l];
            return;
        }

        s.valid = true;
        s.min_x = dat[l].min_x;
        const i64 split_x = dat[r].min_x;
        Lazy acc_l{};
        Lazy acc_r{};
        Point a = dat[l].lb;
        Point b = dat[l].rb;
        Point c = dat[r].lb;
        Point d = dat[r].rb;

        auto move_left = [&](bool go_right) {
            acc_l = compose(acc_l, lazy[l]);
            l = 2 * l + (go_right ? 1 : 0);
            a = mapping(dat[l].lb, acc_l);
            b = mapping(dat[l].rb, acc_l);
        };

        auto move_right = [&](bool go_right) {
            acc_r = compose(acc_r, lazy[r]);
            r = 2 * r + (go_right ? 1 : 0);
            c = mapping(dat[r].lb, acc_r);
            d = mapping(dat[r].rb, acc_r);
        };

        while (a.x != b.x or c.x != d.x) {
            if (a.x != b.x) {
                int ll = 2 * l;
                int lr = ll + 1;
                if (!dat[ll].valid or !dat[lr].valid) {
                    move_left(dat[lr].valid);
                    continue;
                }
            }
            if (c.x != d.x) {
                int rl = 2 * r;
                int rr = rl + 1;
                if (!dat[rl].valid or !dat[rr].valid) {
                    move_right(dat[rr].valid);
                    continue;
                }
            }
            i128 s1 = cross(a, b, c);
            if (a.x != b.x && s1 > 0) move_left(false);
            else if (c.x != d.x && cross(b, c, d) > 0) move_right(true);
            else if (a.x == b.x) move_right(false);
            else if (c.x == d.x) move_left(true);
            else {
                i128 s2 = cross(b, a, d);
                if ( s1 + s2 == 0 || s1 * (i128)(d.x - split_x) < s2 * (i128)(split_x - c.x)) move_left(true);
                else move_right(false);
            }
        }
        s.lb = a;
        s.rb = c;
    }

    // void set(int pos, optional<Point> p) {
    //     set(1, 0, sz, pos, p);
    // }
    //
    // void set(int k, int l, int r, int pos, optional<Point> p) {
    //     if (r - l == 1) {
    //         if (p) dat[k] = Node{true, *p, *p, p->x};
    //         else dat[k] = Node{};
    //         return;
    //     }
    //     push(k);
    //     int mid = (l + r) / 2;
    //     if (pos < mid) set( 2 * k, l, mid, pos, p);
    //     else set( 2 * k + 1, mid, r, pos, p);
    //     pull(k);
    // }
    //
    // void apply(int p, int q, const array<Lazy, 3>& ar) {
    //     apply(1, 0, sz, p, q, ar);
    // }
    //
    // void apply(int k, int l, int r, int p, int q, const array<Lazy, 3>& ar) {
    //     if (!dat[k].valid) return;
    //     if (r <= p) {
    //         all_apply(k, ar[0]);
    //         return;
    //     }
    //     if (q <= l) {
    //         all_apply(k, ar[2]);
    //         return;
    //     }
    //     if (p <= l and r <= q) {
    //         all_apply(k, ar[1]);
    //         return;
    //     }
    //     push(k);
    //     int mid = (l + r) / 2;
    //     apply(2 * k, l, mid, p, q, ar);
    //     apply(2 * k + 1, mid, r, p, q, ar);
    //     pull(k);
    // }

    struct Update {
        int sep1, sep2, erase_at, create_at;
        Point p;
        array<Lazy, 3> lazies;
    };

    void apply(const Update &u) { apply(1, 0, sz, u); }

    void apply(int k, int l, int r, const Update &u) {
        bool to_create = (l <= u.create_at and u.create_at < r);
        if (!dat[k].valid and !to_create) return;
        if (r - l == 1) {
            if (l == u.erase_at) dat[k] = {};
            else if (to_create) dat[k] = Node{true, u.p, u.p, u.p.x};
            else {
                if (l < u.sep1) all_apply(k, u.lazies[0]);
                else if(l < u.sep2) all_apply(k, u.lazies[1]);
                else all_apply(k, u.lazies[2]);
            }
            return;
        }
        bool to_erase = (l <= u.erase_at and u.erase_at < r);
        if (!to_erase and !to_create) {
            if (r <= u.sep1) {
                all_apply(k, u.lazies[0]);
                return;
            }
            if (u.sep2 <= l) {
                all_apply(k, u.lazies[2]);
                return;
            }
            if (u.sep1 <= l and r <= u.sep2) {
                all_apply(k, u.lazies[1]);
                return;
            }
        }
        push(k);
        int mid = (l + r) / 2;
        apply(2 * k, l, mid, u);
        apply(2 * k + 1, mid, r, u);
        pull(k);
    }

    i128 all_prod() {
        int k = 1;
        while (k < sz) {
            push(k);
            int l = 2 * k;
            int r = l + 1;
            if (!dat[l].valid) k = r;
            else if (!dat[r].valid) k = l;
            else if (dat[k].lb.y <= dat[k].rb.y) k = l;
            else k = r;
        }
        return dat[k].lb.y;
    }
};

#include "atcoder/fenwicktree.hpp"
using Point = DynamicLowerHull::Point;
using Lazy = DynamicLowerHull::Lazy;
using Update = DynamicLowerHull::Update;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n, m, q; cin >> n >> m >> q;
    vector<i64> xs;
    vector<i64> a(n);
    vector<pair<int, i64>> qs(q);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] %= m;
        xs.emplace_back(a[i]);
    }
    for (int i = 0; i < q; i++) {
        cin >> qs[i].first >> qs[i].second;
        qs[i].first--;
        qs[i].second %= m;
        xs.emplace_back(qs[i].second);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    int k = xs.size();
    vector<int> freq(k);
    atcoder::fenwick_tree<i64> ft0(k), ft1(k);
    i64 s = 0; i128 c = 0;
    vector<optional<Point>> init(k);

    for (i64 x : a) {
        s += x;
        int xi = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        freq[xi]++;
    }
    i64 cnt_lt = 0, sum_lt = 0;
    for (int i = 0; i < k; i++) if (freq[i] > 0){
        i128 f = (i128)n * 2 * sum_lt - (i128)s * 2 * cnt_lt + (i128)m * cnt_lt * (n-cnt_lt);
        init[i] = Point{cnt_lt, (i64)f};
        c += ((i128)xs[i] * cnt_lt - sum_lt) * freq[i];
        cnt_lt += freq[i];
        sum_lt += freq[i] * xs[i];
        ft0.add(i, freq[i]);
        ft1.add(i, freq[i] * xs[i]);
    }
    DynamicLowerHull hull(init);

    for (auto [pos, y] : qs) {
        i64 x = a[pos];
        if (x == y) {
            i128 ans = c + hull.all_prod();
            cout << (i64)ans << "\n";
            continue;
        }
        int xi = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        int yi = lower_bound(xs.begin(), xs.end(), y) - xs.begin();
        i64 d = y - x;
        bool del_x = (--freq[xi] == 0);
        bool add_y = (freq[yi]++ == 0);
        // if (del_x) hull.set(xi, nullopt);
        array<Lazy, 3> ar;
        ar[0] = Lazy{0, -2*d, 0};
        ar[2] = Lazy{0, -2*d, (i128)n * d * 2};
        if (x < y) {
            ar[1] = Lazy{-1, 2 * (m-d), 2 * (i128)(s+d) - 2 * (i128)n * x - (i128)m * (n+1)};
        }
        else {
            ar[1] = Lazy{1, -2 * (m+d), -2 * (i128)(s+d) + 2 * (i128)n * y + (i128)m * (n-1)};
        }
        // hull.apply(min(xi,yi)+1, max(xi,yi)+1, ar);

        {
            cnt_lt = ft0.sum(0, xi);
            sum_lt = ft1.sum(0, xi);
            i64 cnt_gt = ft0.sum(xi+1, k);
            i64 sum_gt = ft1.sum(xi+1, k);
            c -= (i128)x * cnt_lt - sum_lt + sum_gt - (i128)x * cnt_gt;
        }
        ft0.add(xi, -1); ft1.add(xi, -x);
        {
            cnt_lt = ft0.sum(0, yi);
            sum_lt = ft1.sum(0, yi);
            i64 cnt_gt = ft0.sum(yi+1, k);
            i64 sum_gt = ft1.sum(yi+1, k);
            c += (i128)y * cnt_lt - sum_lt + sum_gt - (i128)y * cnt_gt;
        }
        ft0.add(yi, 1); ft1.add(yi, y);
        s += d;
        a[pos] = y;

        Update u;
        u.sep1 = min(xi, yi) + 1;
        u.sep2 = max(xi, yi) + 1;
        u.create_at = (add_y ? yi : -1);
        u.erase_at = (del_x ? xi : -1);
        u.lazies = ar;

        if (add_y) {
            cnt_lt = ft0.sum(0, yi);
            sum_lt = ft1.sum(0, yi);
            i128 f = (i128)n * 2 * sum_lt - (i128)s * 2 * cnt_lt + (i128)m * cnt_lt * (n-cnt_lt);
            // hull.set(yi, Point{cnt_lt, (i64)f});
            u.p = Point{cnt_lt, (i64)f};
        }
        else u.p = Point{};

        hull.apply(u);

        i128 ans = c + hull.all_prod();
        cout << (i64)ans << "\n";
    }
}