Language: C++

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

const int QMAX = 5*1e5;

// 1-indexed
int n;
int data[QMAX+1];

// a[i]
int sum(int i)
{
	int s = 0;
	while (i > 0) {
		s += data[i];
		i -= i & -i;
	}
	return s;
}

// add x to a[l]..a[r-1]
void add(int l, int r, int x)
{
	while (l <= n) {
		data[l] += x;
		l += l & -l;
	}
	while (r <= n) {
		data[r] -= x;
		r += r & -r;
	}
}

const int NMAX = 5*1e5;

int N, Q;
int c[NMAX+1];
vector<P> tm_st, tm_end;

int ans[QMAX+1];
int tm_corres[QMAX+1];

int prv[NMAX+1];

int main()
{
	scanf("%d%d", &N, &Q);
	tm_st.resize(Q);
	tm_end.resize(Q);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &c[i+1]);
	}
	for (int i = 0; i < Q; ++i) {
		int l, r;
		scanf("%d%d", &l, &r);
		tm_st[i] = make_pair(l, i+1);
		tm_end[i] = make_pair(r, i+1);
	}
	sort(tm_st.begin(), tm_st.end());
	sort(tm_end.begin(), tm_end.end());
	int st_index = 0; // i ha [0,st_index-1) ni eikyou suru
	int end_index = 0;

	for (auto ite = tm_st.begin(); ite != tm_st.end(); ++ite) {
		tm_corres[ite->second] = ite - tm_st.begin() + 1;
	}

	memset(prv, -1, sizeof(prv));
	n = Q;

	for (int i = 1; i <= N+1; ++i) {
		while (end_index < Q && tm_end[end_index].first < i) {
			ans[tm_end[end_index].second]
				= sum(tm_corres[tm_end[end_index].second]);
			//printf("write %d %d\n", tm_end[end_index].second, ans[tm_end[end_index].second]);
			++end_index;
		}

		if (i == N+1) break;

		while (st_index < Q && tm_st[st_index].first <= i) {
			++st_index;
		}

		int l = 1;
		if (prv[c[i]] != -1) {
			l = lower_bound(tm_st.begin(), tm_st.end(),
					make_pair(prv[c[i]]+1,0))-tm_st.begin()+1;
			//printf("prv: %d\n", prv[c[i]]);
			//fflush(stdout);
		}
		prv[c[i]] = i;

		add(l, st_index + 1, 1);
		//printf("add [%d,%d)\n", l, st_index);
		//fflush(stdout);

		/*
		printf("i: %d, ", i);
		for (int j = 1; j <= Q; ++j)
			printf("\t%d: %d\n", j, sum(j));
		fflush(stdout);
		*/
	}

	for (int i = 1; i <= Q; ++i) {
		printf("%d\n", ans[i]);
	}

	return 0;
}



Compiler output:
a.cc: In function 'int sum(int)':
a.cc:22:22: error: reference to 'data' is ambiguous
   22 |                 s += data[i];
      |                      ^~~~
In file included from /usr/include/c++/14/vector:69,
                 from a.cc:4:
/usr/include/c++/14/bits/range_access.h:344:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  344 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:334:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  334 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:323:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  323 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:312:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  312 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
a.cc:15:5: note:                 'int data [500001]'
   15 | int data[QMAX+1];
      |     ^~~~
a.cc: In function 'void add(int, int, int)':
a.cc:32:17: error: reference to 'data' is ambiguous
   32 |                 data[l] += x;
      |                 ^~~~
/usr/include/c++/14/bits/range_access.h:344:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  344 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:334:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  334 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:323:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  323 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:312:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  312 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
a.cc:15:5: note:                 'int data [500001]'
   15 | int data[QMAX+1];
      |     ^~~~
a.cc:36:17: error: reference to 'data' is ambiguous
   36 |                 data[r] -= x;
      |                 ^~~~
/usr/include/c++/14/bits/range_access.h:344:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  344 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:334:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  334 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:323:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  323 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:312:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  312 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
a.cc:15:5: note:                 'int data [500001]'
   15 | int data[QMAX+1];
      |     ^~~~