結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー elphe
提出日時 2025-08-18 01:16:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 509 ms / 2,500 ms
コード長 6,662 bytes
コンパイル時間 4,358 ms
コンパイル使用メモリ 288,680 KB
実行使用メモリ 26,104 KB
最終ジャッジ日時 2025-09-06 12:33:50
合計ジャッジ時間 18,692 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

namespace MyLib
{
	template<typename T, class Picker, T default_value> class LiteralSegmentTree
	{
	protected:
		std::vector<std::vector<T>> containers;
	
	public:
		constexpr LiteralSegmentTree(const std::vector<T>& initializer)
		{
			containers.clear();
	
			if (initializer.size() == 0) return;
			else if (initializer.size() == 1) { containers.emplace_back(1, initializer[0]); return; }
	
			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}
	
			containers.emplace_back((uint_fast32_t)1 << r);
	
			uint_fast32_t i;
			for (i = 0; i != initializer.size(); ++i)
				containers[0][i] = initializer[i];
			for (; i != ((uint_fast32_t)1 << r); ++i)
				containers[0][i] = default_value;
	
			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}
	
		constexpr LiteralSegmentTree(std::vector<T>&& initializer)
		{
			containers.clear();
	
			if (initializer.size() == 0) return;
	
			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}
	
			containers.emplace_back(std::move(initializer));
			containers[0].resize((uint_fast32_t)1 << r, default_value);
	
			uint_fast32_t i;
			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}
	
		constexpr LiteralSegmentTree(const uint_fast32_t n) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, default_value)) { }
		constexpr LiteralSegmentTree(const uint_fast32_t n, const T initial_value) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, initial_value)) { }
	
		[[nodiscard]] constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; }
	
		[[nodiscard]] constexpr uint_fast32_t size() const noexcept { return containers[0].size(); }
		[[nodiscard]] constexpr uint_fast32_t layer() const noexcept { return containers.size(); }
	
		constexpr T update(uint_fast32_t index, const T value) noexcept
		{
			containers[0][index] = value;
	
			index >>= 1;
			for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1)
				containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]);
	
			return value;
		}
	
		[[nodiscard]] constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept
		{
			if (containers.size() == 0 || end_index > containers[0].size()) return default_value;
	
			T ret_l = default_value, ret_r = default_value;
			for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer)
			{
				if (first_index & 1)
					ret_l = Picker()(ret_l, containers[cur_layer][first_index]), ++first_index;
				if (end_index & 1)
					ret_r = Picker()(containers[cur_layer][end_index - 1], ret_r);
			}
	
			return Picker()(ret_l, ret_r);
		}
	};
}

[[nodiscard]] static inline constexpr int_fast64_t init_ans(const uint_fast32_t N, const uint_fast32_t M, const std::vector<int_fast32_t>& A, const std::vector<int_fast64_t>& B, const std::vector<int_fast32_t>& L, const std::vector<int_fast32_t>& R) noexcept
{
	int_fast64_t cur_ans = 0;
	std::vector<int_fast64_t> csum_B(M + 2, 0);
	for (uint_fast32_t i = 1; i <= M; ++i)
		csum_B[i + 1] = csum_B[i] + B[i];

	for (uint_fast32_t i = 1; i <= N; ++i)
		cur_ans += static_cast<int_fast64_t>(R[i] - L[i] + 1) * A[i] - (csum_B[R[i] + 1] - csum_B[L[i]]);

	return cur_ans;
}

[[nodiscard]] static inline constexpr std::vector<int_fast64_t> solve(const uint_fast32_t N, const uint_fast32_t M, const uint_fast32_t Q, const std::vector<int_fast32_t>& A, std::vector<int_fast32_t>& L, std::vector<int_fast32_t>& R, const std::vector<int_fast32_t>& X, const std::vector<int_fast32_t>& Y, const std::vector<int_fast32_t>& U, const std::vector<int_fast32_t>& V) noexcept
{
	std::vector<int_fast32_t> addr_of(N + 1), imos_weight_initializer(M + 2, 0);
	std::vector<int_fast64_t> B_initializer(M + 1, 0);
	for (uint_fast32_t i = 1; i <= N; ++i)
		B_initializer[addr_of[i] = i] = A[i], ++imos_weight_initializer[L[i]], --imos_weight_initializer[R[i] + 1];

	int_fast64_t cur_ans = init_ans(N, M, A, B_initializer, L, R);
	MyLib::LiteralSegmentTree<int_fast64_t, std::plus<int_fast64_t>, 0> B(std::move(B_initializer));
	MyLib::LiteralSegmentTree<int_fast32_t, std::plus<int_fast32_t>, 0> imos_weight(std::move(imos_weight_initializer));
	std::vector<int_fast64_t> ans(Q);
	for (uint_fast32_t i = 0; i != Q; ++i)
	{
		imos_weight.update(L[X[i]], imos_weight[L[X[i]]] - 1), imos_weight.update(R[X[i]] + 1, imos_weight[R[X[i]] + 1] + 1);
		cur_ans -= static_cast<int_fast64_t>(R[X[i]] - L[X[i]] + 1) * A[X[i]] - B.range_pick_up(L[X[i]], R[X[i]] + 1) - static_cast<int_fast64_t>(imos_weight.range_pick_up(0, addr_of[X[i]] + 1)) * A[X[i]];
		B.update(addr_of[X[i]], 0);
		L[X[i]] = U[i], R[X[i]] = V[i];
		B.update(addr_of[X[i]] = Y[i], A[X[i]]);
		cur_ans += static_cast<int_fast64_t>(R[X[i]] - L[X[i]] + 1) * A[X[i]] - B.range_pick_up(L[X[i]], R[X[i]] + 1) - static_cast<int_fast64_t>(imos_weight.range_pick_up(0, addr_of[X[i]] + 1)) * A[X[i]];
		imos_weight.update(L[X[i]], imos_weight[L[X[i]]] + 1), imos_weight.update(R[X[i]] + 1, imos_weight[R[X[i]] + 1] - 1);
		ans[i] = cur_ans;
	}

	return ans;
}

static inline void output(const uint_fast32_t Q, const std::vector<int_fast64_t>& ans) noexcept
{
	for (uint_fast32_t i = 0; i != Q; ++i)
		std::cout << ans[i] << '\n';
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t N, M, Q, i;
	std::cin >> N >> M;
	std::vector<int_fast32_t> A(N + 1), L(N + 1), R(N + 1);
	for (i = 1; i <= N; ++i)
		std::cin >> A[i] >> L[i] >> R[i];

	std::cin >> Q;
	std::vector<int_fast32_t> X(Q), Y(Q), U(Q), V(Q);
	for (i = 0; i != Q; ++i)
		std::cin >> X[i] >> Y[i] >> U[i] >> V[i];

	output(Q, solve(N, M, Q, A, L, R, X, Y, U, V));
	return 0;
}
0