結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー しもりん
提出日時 2025-09-06 16:51:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 971 ms / 2,500 ms
コード長 11,216 bytes
コンパイル時間 4,184 ms
コンパイル使用メモリ 294,288 KB
実行使用メモリ 31,064 KB
最終ジャッジ日時 2025-09-06 16:51:55
合計ジャッジ時間 29,307 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>
#include <atcoder/modint>
#elif defined(LOCAL)
#include <atcoder/pch.hpp>
#endif

// ――――――――――――――――――――――――――――――――
//  abbreviation
// ――――――――――――――――――――――――――――――――
using namespace std;
using namespace atcoder;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = V<double>;
using vs = V<string>;
using vc = V<char>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using si = set<int>;
using mi = multiset<int>;
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
using mint = modint998244353;
using vm = V<mint>;
using vvm = VV<mint>;

// ――――――――――――――――――――――――――――――――
//  P
// ――――――――――――――――――――――――――――――――
template <typename T, typename U>
struct P : pair<T, U> {
    template <typename... Args>
    P(Args... args) : pair<T, U>(args...) {
    }

    using pair<T, U>::first;
    using pair<T, U>::second;

    P& operator+=(const P& r) {
        first += r.first;
        second += r.second;
        return *this;
    }
    P& operator-=(const P& r) {
        first -= r.first;
        second -= r.second;
        return *this;
    }
    P& operator*=(const P& r) {
        first *= r.first;
        second *= r.second;
        return *this;
    }
    template <typename S>
    P& operator*=(const S& r) {
        first *= r, second *= r;
        return *this;
    }
    P operator+(const P& r) const {
        return P(*this) += r;
    }
    P operator-(const P& r) const {
        return P(*this) -= r;
    }
    P operator*(const P& r) const {
        return P(*this) *= r;
    }
    template <typename S>
    P operator*(const S& r) const {
        return P(*this) *= r;
    }
    P operator-() const {
        return P{-first, -second};
    }
};
using pl = P<ll, ll>;
using pi = P<int, int>;
using vp = V<pl>;

// ――――――――――――――――――――――――――――――――
//  preprocessor
// ――――――――――――――――――――――――――――――――
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define call(v) (v).cbegin(), (v).cend()
#define each(i, v) for (auto i : (v))
#define each2(x, y, v) for (auto [x, y] : (v))
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define repit(i, v) for (auto i = v.begin(); i < v.end(); i++)
#define reprit(i, v) for (auto i = v.rbegin(); i < v.rend(); i++)
#define reg(i, l, r) for (ll i = (ll)(l); i < (ll)(r); i++)
#define regr(i, l, r) for (ll i = (ll)(r) - 1; i >= (ll)(l); i--)
#define regit(i, l, r) for (auto i = (l); i != (r); i++)
#define regrit(i, l, r) for (auto i = make_reverse_iterator((r)); i != make_reverse_iterator((l)); i++)
#define REP(i, n) for (ll i = 0; i <= (ll)(n); i++)
#define REPR(i, n) for (ll i = (ll)(n); i >= 0; i--)
#define REG(i, l, r) for (ll i = (ll)(l); i <= (ll)(r); i++)
#define REGR(i, l, r) for (ll i = (ll)(r); i >= (ll)(l); i--)
#define Yes cout << "Yes" << el
#define No cout << "No" << el
#define YES cout << "YES" << el
#define NO cout << "NO" << el
#define fls cout << flush
#define eps (1e-10)
#define Equals(a, b) (fabs((a) - (b)) < eps)
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define BIT(n) (1LL << (n))
#define between(l, k, r) (l <= k && k < r)
#define pb push_back
// #define fi first
// #define se second

// ――――――――――――――――――――――――――――――――
//  constexpr
// ――――――――――――――――――――――――――――――――
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr string_view ascii_lowercase = "abcdefghijklmnopqrstuvwxyz";
constexpr string_view ascii_uppercase = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr char el = '\n';
constexpr char spa = ' ';

// ――――――――――――――――――――――――――――――――
//  yn, YN
// ――――――――――――――――――――――――――――――――
bool yn(const bool b) {
    if (b) {
        Yes;
    } else {
        No;
    }
    return b;
}

bool YN(const bool b) {
    if (b) {
        YES;
    } else {
        NO;
    }
    return b;
}

// ――――――――――――――――――――――――――――――――
//  chmax, chmin
// ――――――――――――――――――――――――――――――――
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

// ――――――――――――――――――――――――――――――――
//  operator <<, >> overload
// ――――――――――――――――――――――――――――――――
template <typename T>
istream& operator>>(istream& is, V<T>& v) {
    T x;
    is >> x;
    v.push_back(x);
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const V<T>& v) {
    if (&os == &cout) {
        rep(i, v.size()) {
            os << v[i];
            if (i != v.size() - 1) os << ' ';
        }
        return os;
    } else {
        os << "[";
        rep(i, v.size()) {
            os << v[i];
            if (i != v.size() - 1) os << ", ";
        }
        return os << "]";
    }
}

template <class T, class U>
istream& operator>>(istream& is, pair<T, U>& p) {
    return is >> p.first >> p.second;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    if (&os == &cout)
        return os << p.first << ' ' << p.second;
    else
        return os << "(" << p.first << ", " << p.second << ")";
}

template <class... Ts>
istream& operator>>(istream& is, tuple<Ts...>& t) {
    apply(
        [&](const auto&... args) {
            size_t n = 0;
            ((is >> args), ...);
        },
        t);
    return is;
}
template <class... Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
    if (&os == &cout) {
        apply(
            [&](const auto&... args) {
                size_t n = 0;
                ((os << (n++ ? " " : "") << args), ...);
            },
            t);
        return os << ")";
    } else {
        os << "(";
        apply(
            [&](const auto&... args) {
                size_t n = 0;
                ((os << (n++ ? ", " : "") << args), ...);
            },
            t);
        return os << ")";
    }
}

template <int MOD>
istream& operator>>(istream& is, static_modint<MOD>& m) {
    int x;
    is >> x;
    m = static_modint<MOD>(x);
    return is;
}
template <int MOD>
ostream& operator<<(ostream& os, const static_modint<MOD>& m) {
    return os << m.val();
}

// ――――――――――――――――――――――――――――――――
//  factotrial
// ――――――――――――――――――――――――――――――――
vm fact, invf;
void fact_init(int m = 200000) {
    fact.resize(m + 1);
    invf.resize(m + 1);
    fact[0] = 1;
    rep(i, m) fact[i + 1] = fact[i] * (i + 1);
    invf[m] = fact[m].inv();
    repr(i, m) invf[i] = invf[i + 1] * (i + 1);
}
mint comb(int n, int r) {
    if (r < 0 || n < r) return 0;
    return fact[n] * invf[r] * invf[n - r];
}
mint noadj(int n, int r) {
    return comb(n - r + 1, r);
}

// ――――――――――――――――――――――――――――――――
//  Fibonacci
// ――――――――――――――――――――――――――――――――
vm fib;
void fib_init(int m = 200000) {
    fib.resize(m + 1);
    fib[0] = 0;
    fib[1] = 1;
    rep(i, m) fib[i + 2] = fib[i] + fib[i + 1];
}

// ――――――――――――――――――――――――――――――――
//  monoid
// ――――――――――――――――――――――――――――――――
namespace monoid {
struct S {
    ll value;
    int len;
};

using F = int;

S op(S l, S r) {
    return S{
        l.value + r.value,
        l.len + r.len,
    };
}

S e() {
    return S{0, 0};
}

S mapping(F l, S r) {
    return S{
        r.value + l * r.len,
        r.len,
    };
}

F composition(F l, F r) {
    return l + r;
}

F id() {
    return 0;
}
}  // namespace monoid

// ――――――――――――――――――――――――――――――――
//  ACL
// ――――――――――――――――――――――――――――――――
// #include <atcoder/fenwicktree>
// #include <atcoder/segtree>
#include <atcoder/lazysegtree>
// #include <atcoder/string>
// #include <atcoder/math>
// #include <atcoder/convolution>
// #include <atcoder/dsu>
// #include <atcoder/maxflow>
// #include <atcoder/mincostflow>
// #include <atcoder/scc>
// #include <atcoder/twosat>

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10) << boolalpha;
    cerr << fixed << setprecision(10) << boolalpha;

    int N, M;
    cin >> N >> M;
    vl A;
    vp itv;
    rep(i, N) {
        cin >> A >> itv;
        itv[i].first--;
    }
    vi H(N);
    rep(i, N) H[i] = i;
    vi C(M + 1, 0);
    each2(l, r, itv) {
        C[l]++;
        C[r]--;
    }
    rep(i, M) C[i + 1] += C[i];
    ll ans = 0;
    rep(i, N) {
        int a = A[i];
        auto [l, r] = itv[i];
        int c = C[i];
        ans += (r - l - c) * a;
    }
    lazy_segtree<
        monoid::S,
        monoid::op,
        monoid::e,
        monoid::F,
        monoid::mapping,
        monoid::composition,
        monoid::id>
        TB(M);
    lazy_segtree<
        monoid::S,
        monoid::op,
        monoid::e,
        monoid::F,
        monoid::mapping,
        monoid::composition,
        monoid::id>
        TC(M);
    rep(i, N) TB.set(i, monoid::S{A[i], 1});
    rep(i, M) TC.set(i, monoid::S{C[i], 1});
    int Q;
    cin >> Q;
    cerr << ans << el;
    rep(i, Q) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        x--;
        y--;
        u--;
        ll a = A[x];
        int yy = H[x];
        H[x] = y;
        auto [l, r] = itv[x];
        itv[x] = make_pair(u, v);
        ans += ((v - u) - (r - l)) * a;
        ans += TB.prod(l, r).value;
        TB.set(yy, monoid::S{0, 1});
        TB.set(y, monoid::S{a, 1});
        ans -= TB.prod(u, v).value;
        TC.apply(l, r, -1);
        ans -= (TC.get(y).value - TC.get(yy).value) * a;
        TC.apply(u, v, 1);
        cout << ans << el;
    }

    return 0;
}
0