评测记录

#include <bits/stdc++.h>


class cin final {
public:
    inline cin operator>>(int &Num) {
        Num = 0;
        int C = getchar();
        while (C < '0' || C > '9') C = getchar();
        while (C >= '0' && C <= '9') {
            Num = Num * 10 + (C ^ '0');
            C = getchar();
        }
        return *this;
    }
}cin;


class cout final {
public:
    inline cout operator<<(int Num) {
        if (Num >= 10) {
            *this << (Num / 10);
        }
        putchar(Num % 10 ^ '0');
        return *this;
    }
    inline cout operator<<(char C) {
        putchar(C);
        return *this;
    }
}cout;


const int MAX = 1e6 + 5;


int N{}, A[MAX]{}, Q{};
int BlockLen{}, L = 1, R{},  BlockNum{};
int Sum{}, Ans[MAX]{}, Cnt[MAX]{};


int Belong[MAX]{};
int Flag[MAX]{}, Pre[MAX]{}, Suf[MAX]{};


struct COpt {
	int L{}, R{}, Id{};
}Opt[MAX];


int main() {
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	BlockLen = sqrt(N);
	if (N % BlockLen) BlockNum++;
	for (int i = 1; i <= N; ++i) Belong[i] = (i - 1) / BlockLen + 1;
	cin >> Q;
	for (int i = 1; i <= Q; ++i) cin >> Opt[i].L >> Opt[i].R, Opt[i].Id = i;

	std::sort(Opt + 1, Opt + 1 + Q, [](COpt A, COpt B) {
		if (Belong[A.L] != Belong[B.L]) return A.L < B.L;
		else if (Belong[A.L] & 1) return A.R < B.R;
		else return A.R > B.R;
	});

	for (int i = 1; i <= N; ++i) Pre[i] = Flag[A[i]], Flag[A[i]] = i;

	memset(Flag, 0x3f, sizeof(Flag));
	for (int i = N; i >= 1; --i) Suf[i] = Flag[A[i]], Flag[A[i]] = i;

	for (int i = 1; i <= Q; ++i) {
		while (L > Opt[i].L) Sum += (Suf[--L] > R);
		while (L < Opt[i].L) Sum -= (Suf[L++] > R);
		while (R > Opt[i].R) Sum -= (Pre[R--] < L);
		while (R < Opt[i].R) Sum += (Pre[++R] < L);
		Ans[Opt[i].Id] = Sum;
	}

	for (int i = 1; i <= Q; ++i) cout << Ans[i] << '\n';
}