WA代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 3e4 + 1, maxm = 2e5 + 1, limit = 1e6 + 1;
struct query
{
	int l, r, num;
}q[maxm];
int n, m, l = 1, r, now, size, block[maxn], cnt[limit], a[maxn], ans[maxn];  
inline int read()
{
	register int s = 0;
	char ch = getchar();
	while(ch > '9' || ch < '0')
	{
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s;
}
inline void write(int x){
	if(x > 9)
	{
		write(x / 10);
	}
	putchar((x % 10) ^ 48);
}
inline bool cmp(query a,query b){
	if(block[a.l] ^ block[b.l])
	{
		return block[a.l] < block[b.l];
	}
	else if(block[a.l] & 1)
	{
		return a.r < b.r;
	}
	return a.r > b.r;
}
int main()
{
	n = read();
	size = ceil(pow(n, 0.5));
	for(register int i = 1; i <= n; ++i)
	{
		block[i] = (i - 1) / size + 1;
		a[i] = read();
	}
	m = read();
	for(register int i = 1; i <= m; ++i)
	{
		q[i] = (query) 
		{
			read(), read(), i
		};
	}
	sort(q + 1, q + 1 + m, cmp);
	for(register int i = 1; i <= m; ++i)
	{
		while(l < q[i].l)
		{
			now -= !--cnt[a[l++]];
		}
		while(l > q[i].l)
		{
			now += !cnt[a[--l]]++;
		}
		while(r > q[i].r)
		{
			now -= !--cnt[a[r--]];
		}
		while(r < q[i].r)
		{
			now += !cnt[a[++r]]++;
		}
		ans[q[i].num] = now;
	}
	for(register int i = 1; i <= m; ++i)
	{
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}

AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 3e5 + 1, maxm = 2e5 + 1, limit = 1e6 + 1;
struct query
{
	int l, r, num;
}q[maxm];
int n, m, l = 1, r, now, size, block[maxn], cnt[limit], a[maxn], ans[maxn];  
inline int read()
{
	register int s = 0;
	char ch = getchar();
	while(ch > '9' || ch < '0')
	{
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s;
}
inline void write(int x){
	if(x > 9)
	{
		write(x / 10);
	}
	putchar((x % 10) ^ 48);
}
inline bool cmp(query a,query b){
	if(block[a.l] ^ block[b.l])
	{
		return block[a.l] < block[b.l];
	}
	else if(block[a.l] & 1)
	{
		return a.r < b.r;
	}
	return a.r > b.r;
}
int main()
{
	n = read();
	size = ceil(pow(n, 0.5));
	for(register int i = 1; i <= n; ++i)
	{
		block[i] = (i - 1) / size + 1;
		a[i] = read();
	}
	m = read();
	for(register int i = 1; i <= m; ++i)
	{
		q[i] = (query) 
		{
			read(), read(), i
		};
	}
	sort(q + 1, q + 1 + m, cmp);
	for(register int i = 1; i <= m; ++i)
	{
		while(l < q[i].l)
		{
			now -= !--cnt[a[l++]];
		}
		while(l > q[i].l)
		{
			now += !cnt[a[--l]]++;
		}
		while(r > q[i].r)
		{
			now -= !--cnt[a[r--]];
		}
		while(r < q[i].r)
		{
			now += !cnt[a[++r]]++;
		}
		ans[q[i].num] = now;
	}
	for(register int i = 1; i <= m; ++i)
	{
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}

都是莫队加优化 可因为maxn的范围使我WA