提出 #15664290

---

ソースコード 拡げる

#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define endl '\n'
#ifndef CODE_JAM
#undef CASE_INFO
#endif
#else
#pragma GCC optimize "trapv"
#endif
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(n) for(int i = 0; i < n; i++)
#define repj(n) for(int j = 0; j < n; j++)
#define all(p) p.begin(), p.end()
#define count_1(p) __builtin_popcountll(p)
#define count_0(p) __builtin_ctzll(p)
using namespace std;
template<class X=int>inline X mid(X s,X e){return (s+(e-s)/2);}
template<class X=int>inline X len(X s,X e){return (e-s+1);}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const int MOD = 1e9 + 7;
const int oo = 987654321;
const ll OO = 1e18;

class Timer {
public:
	clock_t start;
	Timer() {start = clock();}
	~Timer() {cerr << (double)(clock() - start)/CLOCKS_PER_SEC << "\n";}
};

class MST {
	vector<vector<int>> T;
	int n;
public:
	MST(const vector<int>& A) {
		n = A.size();
		T.assign(2*n, vector<int>());
		for(int p = n; p < 2*n; p++)
			T[p].push_back(A[p - n]);
		for(int p = n - 1; p > 0; p--) {
			T[p].resize(T[p<<1].size() + T[p<<1|1].size());
			merge(all(T[p<<1]), all(T[p<<1|1]), T[p].begin());
		}
	}

	int query(int l, int r) {
		int thresh = l, ret = 0;
		for(l += n, r += n + 1; l < r; l>>=1, r>>=1) {
			if(l & 1) ret += lower_bound(all(T[l]), thresh) - T[l].begin(), l++;
			if(r & 1) --r, ret += lower_bound(all(T[r]), thresh) - T[r].begin();
		}
		return ret;
	}
};

void solve() {
	int n, Q;
	cin >> n >> Q;
	vi c(n); rep(n) cin >> c[i];
	vi cur(n, -1), prevOcc(n, -1);
	for(int i = 0; i < n; i++) {
      c[i]--;
		prevOcc[i] = cur[c[i]];
		cur[c[i]] = i;
	}
	MST mst(prevOcc);
	while(Q--) {
		int l, r;
		cin >> l >> r;
		l--; r--;
		cout << mst.query(l, r) << endl;
	}
}

signed main() {
	Timer ti;
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int T = 1;
	#ifdef TEST_CASES
	cin >> T;
	#endif
	for(int t = 1; t <= T; t++) {
		#ifdef CASE_INFO
		cout << "Case #" << t << ": ";
		#endif
		solve();
	}
	return 0;
}

提出情報

ジャッジ結果