test/ABC242-G.test.cpp

• View this file on GitHub
• Last update: 2023-03-30 00:09:49+09:00
• Problem: https://atcoder.jp/contests/abc242/tasks/abc242_g

Depends on

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

Code

#define PROBLEM "https://atcoder.jp/contests/abc242/tasks/abc242_g"

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

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

int main() {
	int N;
	std::scanf("%d", &N);
	int A[N];
	for (int i = 0 ; i < N ; i++)
		std::scanf("%d", A + i);
	int Q;
	std::scanf("%d", &Q);
	std::vector<std::pair<int, int>> Query(Q);
	for (auto& [l, r] : Query) {
		std::scanf("%d%d", &l, &r);
		--l;
	}
	int mx = *std::max_element(A, A + N) + 1;
	int S[mx];
	std::fill(S, S + mx, 0);
	int ans = 0;
	int Ans[Q];
	int L = 0, R = 0;
	for (const auto& [l, r, index] : zawa::mo(N, Query)) {
		while (R < r) {
			S[A[R]]++;
			if (!(S[A[R]] & 1)) ans++;
			R++;
		}
		while (L > l) {
			L--;
			S[A[L]]++;
			if (!(S[A[L]] & 1)) ans++;
		}
		while (R > r) {
			R--;
			S[A[R]]--;
			if (S[A[R]] & 1) ans--;
		}
		while (L < l) {
			S[A[L]]--;
			if (S[A[L]] & 1) ans--;
			L++;
		}
		Ans[index] = ans;
	}
	for (int i = 0 ; i < Q ; i++)
		std::printf("%d\n", Ans[i]);
}

#line 1 "test/ABC242-G.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc242/tasks/abc242_g"

#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/ABC242-G.test.cpp"

#include <cstdio>
#line 9 "test/ABC242-G.test.cpp"

int main() {
	int N;
	std::scanf("%d", &N);
	int A[N];
	for (int i = 0 ; i < N ; i++)
		std::scanf("%d", A + i);
	int Q;
	std::scanf("%d", &Q);
	std::vector<std::pair<int, int>> Query(Q);
	for (auto& [l, r] : Query) {
		std::scanf("%d%d", &l, &r);
		--l;
	}
	int mx = *std::max_element(A, A + N) + 1;
	int S[mx];
	std::fill(S, S + mx, 0);
	int ans = 0;
	int Ans[Q];
	int L = 0, R = 0;
	for (const auto& [l, r, index] : zawa::mo(N, Query)) {
		while (R < r) {
			S[A[R]]++;
			if (!(S[A[R]] & 1)) ans++;
			R++;
		}
		while (L > l) {
			L--;
			S[A[L]]++;
			if (!(S[A[L]] & 1)) ans++;
		}
		while (R > r) {
			R--;
			S[A[R]]--;
			if (S[A[R]] & 1) ans--;
		}
		while (L < l) {
			S[A[L]]--;
			if (S[A[L]] & 1) ans--;
			L++;
		}
		Ans[index] = ans;
	}
	for (int i = 0 ; i < Q ; i++)
		std::printf("%d\n", Ans[i]);
}

Back to top page