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

• 問題: No.3464 Max and Sum on Grid
• ユーザー: kwm_t
• 提出日時: 2026-03-21 12:14:17
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2,108 ms / 5,000 ms
• コード長: 4,850 bytes
• コンパイル時間: 6,493 ms
• コンパイル使用メモリ: 388,568 KB
• 実行使用メモリ: 20,876 KB
• 最終ジャッジ日時: 2026-03-21 12:14:51
• 合計ジャッジ時間: 27,039 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
pair<long long, long long> op(pair<long long, long long> a, pair<long long, long long> b) {
	return { a.first + b.first,a.second + b.second };
}
pair<long long, long long> e() { return { 0,0 }; }



#ifndef KWM_T_ALGORITHM_MO_HPP
#define KWM_T_ALGORITHM_MO_HPP

#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

/**
 * @brief Mo's Algorithm（区間クエリ順序最適化）
 *
 * クエリ順を並び替えて、区間の追加・削除を amortized に抑える
 *
 * 典型用途:
 *   - 区間内 distinct 数
 *   - 転倒数
 *   - 頻度管理系
 *
 * 計算量:
 *   - O((N + Q) * sqrt(N))
 *
 * @tparam AddL   左に追加 (l--)
 * @tparam AddR   右に追加 (r++)
 * @tparam RemL   左を削除 (l++)
 * @tparam RemR   右を削除 (r--)
 * @tparam Out    クエリ結果出力
 *
 * 制約 / 注意:
 *   - クエリは [l, r) の半開区間
 *   - add/remove は順序に依存しないように設計すること
 *
 * verified:
 *   https://atcoder.jp/contests/awc0015/submissions/74250351
 */
namespace kwm_t::algorithm {

class Mo {
private:
	int n, q;
	int block_size;

	std::vector<int> left, right;
	std::vector<int> order;

public:
	Mo(int n_, int q_) : n(n_), q(q_) {
		block_size = std::max(1, int(n / std::sqrt(q_)));
		order.resize(q_);
		std::iota(order.begin(), order.end(), 0);
	}

	// クエリ設定
	void query(const std::vector<int>& l, const std::vector<int>& r) {
		left = l;
		right = r;
	}

	// 実行
	template<class AddL, class AddR, class RemL, class RemR, class Out>
	void run(AddL add_left, AddR add_right, RemL remove_left, RemR remove_right, Out output) {
		std::sort(order.begin(), order.end(), [&](int a, int b) {
			int ablock = left[a] / block_size;
			int bblock = left[b] / block_size;
			if (ablock != bblock) return ablock < bblock;
			if (ablock & 1) return right[a] < right[b];
			return right[a] > right[b];
			});

		int nl = 0, nr = 0;

		for (int idx : order) {
			while (nl > left[idx]) add_left(--nl);
			while (nr < right[idx]) add_right(nr++);
			while (nl < left[idx]) remove_left(nl++);
			while (nr > right[idx]) remove_right(--nr);

			output(idx);
		}
	}
};

} // namespace kwm_t::algorithm

#endif // KWM_T_ALGORITHM_MO_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, q; cin >> n >> q;
	vector<int>a(n), b(n);
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];

	const int sz = 100000;
	segtree<pair<long long, long long>, op, e>segH(sz + 1);
	segtree<pair<long long, long long>, op, e>segW(sz + 1);

	vector<int>ls, rs;
	rep(i, q) {
		long l, d, r, u; cin >> l >> d >> r >> u;
		l--, d--;
		ls.push_back(l);
		rs.push_back(d);

		ls.push_back(r);
		rs.push_back(u);

		ls.push_back(l);
		rs.push_back(u);

		ls.push_back(r);
		rs.push_back(d);

	}

	kwm_t::algorithm::Mo mo(n, q * 4);
	mo.query(ls, rs);

	long long val = 0;
	int nl = 0, nr = 0;

	// l--
	auto add_left = [&](int i) {
		auto p = segW.prod(a[i], sz + 1);
		val -= p.first;
		val -= 1LL * a[i] * (nr - p.second);
		segH.set(a[i], op({ -a[i], -1 }, segH.get(a[i])));
	};

	// r++
	auto add_right = [&](int i) {
		auto p = segH.prod(b[i], sz + 1);
		val += p.first;
		val += 1LL * b[i] * (nl - p.second);
		segW.set(b[i], op({ b[i], 1 }, segW.get(b[i])));
	};

	// l++
	auto remove_left = [&](int i) {
		auto p = segW.prod(a[i], sz + 1);
		val += p.first;
		val += 1LL * a[i] * (nr - p.second);
		segH.set(a[i], op({ a[i], 1 }, segH.get(a[i])));
	};

	// r--
	auto remove_right = [&](int i) {
		auto p = segH.prod(b[i], sz + 1);
		val -= p.first;
		val -= 1LL * b[i] * (nl - p.second);
		segW.set(b[i], op({ -b[i], -1 }, segW.get(b[i])));
	};

	vector<long long> ans(q);

	auto output = [&](int idx) {
		int i = idx / 4;
		int j = idx % 4;
		if (j < 2) ans[i] += val;
		else ans[i] -= val;
	};

	mo.run(
		[&](int i) { add_left(i); nl--; },
		[&](int i) { add_right(i); nr++; },
		[&](int i) { remove_left(i); nl++; },
		[&](int i) { remove_right(i); nr--; },
		output
	);
	rep(i, q)cout << ans[i] << endl;
	return 0;
}