#1150717 (C++23) No.3464 Max and Sum on Grid

• 問題: No.3464 Max and Sum on Grid
• ユーザー: detteiuu
• 提出日時: 2026-02-28 16:34:09
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2,027 ms / 5,000 ms
• コード長: 4,059 bytes
• コンパイル時間: 8,582 ms
• コンパイル使用メモリ: 400,976 KB
• 実行使用メモリ: 48,892 KB
• 最終ジャッジ日時: 2026-02-28 16:34:40
• 合計ジャッジ時間: 28,982 ms
• ジャッジサーバーID （参考情報）: judge3 / judge7

ファイルパターン	結果
sample	AC * 1
other	AC * 10

ソースコード

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define pass (void)0
#define INF (1<<30)-1
#define INFLL (1LL<<60)-1
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define repr2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define YesNo(cond) cout << ((cond) ? "Yes\n" : "No\n")
#define YESNO(cond) cout << ((cond) ? "YES\n" : "NO\n")

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

template <typename T> void print(const T& value) { cout << value << "\n"; }
template <typename T> void print(const vector<T>& vec) { for (auto& v : vec) cout << v << " "; cout << "\n"; }
template <typename T> void input(vector<T>& vec) { for (auto& v : vec) cin >> v; };
template <typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using vm = vector<mint>;

ll encode(ll l, ll r) {
    return l*1000000+r;
}

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

    ll N, Q;
    cin >> N >> Q;
    vl A(N);
    vl B(N);
    input(A);
    input(B);
    vvl query;
    vector<pll> mquery;
    rep (i, Q) {
        ll l, d, r, u;
        cin >> l >> d >> r >> u;
        l --; d --; r --; u --;
        query.push_back({l, r, d, u});
        mquery.push_back({r, u});
        if (1 <= min(l, d)) mquery.push_back({l-1, d-1});
        if (1 <= l) mquery.push_back({l-1, u});
        if (1 <= d) mquery.push_back({r, d-1});
    }

    ll route = ll(sqrt(N))+1;
    vector<vector<pll>> bucket(N/route+1, vector<pll> ());
    rep (i, sz(mquery)) {
        bucket[mquery[i].first/route].push_back({mquery[i].second, mquery[i].first});
    }
    unordered_map<ll, ll> memo;
    ll now = 0;
    ll left = -1;
    ll right = -1;
    fenwick_tree<ll> F1(100002);
    fenwick_tree<ll> F2(100002);
    fenwick_tree<ll> F3(100002);
    fenwick_tree<ll> F4(100002);
    rep (i, sz(bucket)) {
        if (i%2 == 0) {
                sort(all(bucket[i]));
            } else {
                sort(rall(bucket[i]));
            }
        rep (j, sz(bucket[i])) {
            auto [r, l] = bucket[i][j];
            while (l < left) {
                F1.add(A[left], -1);
                F3.add(A[left], -A[left]);
                now -= A[left]*F2.sum(0, A[left]+1)+F4.sum(A[left]+1, 100002);
                left --;
            }
            while (r < right) {
                F2.add(B[right], -1);
                F4.add(B[right], -B[right]);
                now -= B[right]*F1.sum(0, B[right])+F3.sum(B[right], 100002);
                right --;
            }
            while (left < l) {
                left ++;
                F1.add(A[left], 1);
                F3.add(A[left], A[left]);
                now += A[left]*F2.sum(0, A[left]+1)+F4.sum(A[left]+1, 100002);
            }
            while (right < r) {
                right ++;
                F2.add(B[right], 1);
                F4.add(B[right], B[right]);
                now += B[right]*F1.sum(0, B[right])+F3.sum(B[right], 100002);
            }
            memo[encode(l, r)] = now;
        }
    }
    
    rep (i, Q) {
        ll l1, r1, l2, r2;
        l1 = query[i][0]; r1 = query[i][1]; l2 = query[i][2]; r2 = query[i][3];
        ll a, b, c, d;
        a = 0; b = 0; c = 0; d = 0;
        a = memo[encode(r1, r2)];
        if (1 <= min(l1, l2)) b = memo[encode(l1-1, l2-1)];
        if (1 <= l1) c = memo[encode(l1-1, r2)];
        if (1 <= l2) d = memo[encode(r1, l2-1)];

        print(a+b-c-d);
    }
}