test/data-structure/pbds/yosupo-Static-Range-Frequency.test.cpp

View this file on GitHub
Last update: 2023-07-11 10:41:16+08:00
Problem: https://judge.yosupo.jp/problem/static_range_frequency

Depends on

Code

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

#include <iostream>

#include "../../../library/data-structure/pbds.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	hash_map<int, vector<int>> pos;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		pos[x].push_back(i);
	}
	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		cout << lower_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l) << "\n";
	}
	return 0;
}

#line 1 "test/data-structure/pbds/yosupo-Static-Range-Frequency.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_frequency"

#include <iostream>

#line 2 "library/data-structure/pbds.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#line 2 "library/random/splitmix64.hpp"
#include <chrono>


namespace felix {

namespace internal {

// http://xoshiro.di.unimi.it/splitmix64.c

struct splitmix64_hash {
	static unsigned long long splitmix64(unsigned long long x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	unsigned long long operator()(unsigned long long x) const {
		static const unsigned long long FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

} // namespace internal


} // namespace felix

#line 4 "library/data-structure/pbds.hpp"

namespace felix {

template<class T, class U, class H = internal::splitmix64_hash> using hash_map = __gnu_pbds::gp_hash_table<T, U, H>;
template<class T, class H = internal::splitmix64_hash> using hash_set = hash_map<T, __gnu_pbds::null_type, H>;

} // namespace felix
#line 5 "test/data-structure/pbds/yosupo-Static-Range-Frequency.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	hash_map<int, vector<int>> pos;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		pos[x].push_back(i);
	}
	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		cout << lower_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l) << "\n";
	}
	return 0;
}