test/mo.test.cpp

View this file on GitHub
Last update: 2023-03-30 00:09:49+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

mo (Mo's Algorithm) (src/algorithm/mo.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#include "../src/algorithm/mo.hpp"

#include <cstdio>
#include <vector>
#include <utility>

int main() {
	int N, Q;
	std::scanf("%d%d", &N, &Q);
	std::vector<int> A(N);
	for (int i = 0 ; i < N ; i++)
		std::scanf("%d", &A[i]);
	std::vector<std::pair<int, int>> Query(Q);
	for (int i = 0 ; i < Q ; i++)
		std::scanf("%d%d", &Query[i].first, &Query[i].second);	
	std::vector<long long> Ans(Q);
	long long ans = 0LL;
	int nowl = 0, nowr = 0;
	for (auto [l, r, index] : zawa::mo(N, Query)) {
		while (nowr < r) ans += A[nowr++];
		while (nowl > l) ans += A[--nowl];
		while (nowr > r) ans -= A[--nowr];
		while (nowl < l) ans -= A[nowl++];
		Ans[index] = ans;
	}
	for (int i = 0 ; i < Q ; i++)
		std::printf("%lld\n", Ans[i]);
}

#line 1 "test/mo.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#line 2 "src/algorithm/mo.hpp"

#include <vector>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cmath>

namespace zawa {

std::vector<std::tuple<int, int, int>> mo(int N, const std::vector<std::pair<int, int>>& Q) {
	int sq = std::sqrt(Q.size() + 1);
	std::vector tmp((N + sq - 1) / sq, std::vector(0, std::tuple(0, 0, 0)));
	for (int i = 0 ; i < (int)Q.size() ; i++)
		tmp[Q[i].first / sq].emplace_back(Q[i].second, Q[i].first, i);
	std::vector res(0, std::tuple(0, 0, 0));
	for (int i = 0 ; i < (int)tmp.size() ; i++) {
		std::sort(tmp[i].begin(), tmp[i].end());
		if (i & 1) std::reverse(tmp[i].begin(), tmp[i].end());
		for (const auto& [r, l, index] : tmp[i]) res.emplace_back(l, r, index);
	}
	return res;
}

}// namespace zawa
#line 4 "test/mo.test.cpp"

#include <cstdio>
#line 8 "test/mo.test.cpp"

int main() {
	int N, Q;
	std::scanf("%d%d", &N, &Q);
	std::vector<int> A(N);
	for (int i = 0 ; i < N ; i++)
		std::scanf("%d", &A[i]);
	std::vector<std::pair<int, int>> Query(Q);
	for (int i = 0 ; i < Q ; i++)
		std::scanf("%d%d", &Query[i].first, &Query[i].second);	
	std::vector<long long> Ans(Q);
	long long ans = 0LL;
	int nowl = 0, nowr = 0;
	for (auto [l, r, index] : zawa::mo(N, Query)) {
		while (nowr < r) ans += A[nowr++];
		while (nowl > l) ans += A[--nowl];
		while (nowr > r) ans -= A[--nowr];
		while (nowl < l) ans -= A[nowl++];
		Ans[index] = ans;
	}
	for (int i = 0 ; i < Q ; i++)
		std::printf("%lld\n", Ans[i]);
}