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

• 問題: No.3772 Discrete Addition
• ユーザー: apricity
• 提出日時: 2026-09-28 15:09:18
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,621 ms / 8,000 ms
• コード長: 8,655 bytes
• コンパイル時間: 1,840 ms
• コンパイル使用メモリ: 205,768 KB
• 実行使用メモリ: 48,676 KB
• 最終ジャッジ日時: 2026-10-16 20:56:05
• 合計ジャッジ時間: 8,415 ms
• ジャッジサーバーID （参考情報）: judge3_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);
    }

    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;

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;

        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});
        }

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