题目链接:
为什么要卡莫队!为什么加强的这么毒瘤! 莫队可以拿100分剩下三个点没治了// luogu-judger-enable-o2#include#include #include #include #include #define ri register#define il inlineusing namespace std;const int maxn = 1000001;inline int read(){ int k=0; char c; c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c)){k=(k<<3)+(k<<1)+c-'0';c=getchar();} return k;}int n, m, c, answer, bl, curL = 1, curR = 0;int a[maxn], cnt[maxn], ans[maxn];struct Query{ int l, r, p; friend bool operator < (const Query &a, const Query &b) { return (a.l/bl) == (b.l/bl) ? a.r < b.r : a.l < b.l; }}q[maxn];il void add(int pos){ ++cnt[a[pos]]; if(cnt[a[pos]] == 2) answer++;}il void del(int pos){ --cnt[a[pos]]; if(cnt[a[pos]] == 1) answer--;}int main(){ n = read(); c = read(); m = read(); bl = sqrt(n); for(ri int i = 1; i <= n; i++) a[i] = read(); for(ri int i = 1; i <= m; i++) { int l,r; l = read(); r = read(); q[i].l = l; q[i].r = r; q[i].p = i; } sort(q+1,q+1+m); for(ri int i = 1; i <= m; i++) { int L = q[i].l, R = q[i].r; while(curL < L) del(curL++); while(curL > L) add(--curL); while(curR < R) add(++curR); while(curR > R) del(curR--); ans[q[i].p] = answer; } for(int i = 1; i <= m; i++) printf("%d\n",ans[i]); return 0;}