在做这道莫队的时候全WA掉了.. 然后开始瞎改。

下载第一个数据点测试

交换pos数组和a数组之后，我发现第一个数据点过了..

索性提交WA->AC

?????

不知道有没有dalao告诉我这是为什么..

以下是具体情况：

测试点1输出：

代码1： 3205 20443 7406 14596 5996 21047 36663 44568 26016 32622 40089... 错误

代码2： 3008 20362 7241 14479 5823 20970 36652 44575 25965 32567 40086... 正确

---

附上代码：

代码1：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define rg register
#define il inline
#define MAXN 50010
#define LL long long
using namespace std;

il void init(int &x)
{
	x = 0;
	char c = getchar();
	while(c>'9' || c<'0')	c = getchar();
	while(c>='0' && c<='9')
	{
		x = (x<<1) + (x<<3) +(c^48);
		c = getchar();
	}
}

int n, m, k, rtn, a[MAXN], pos[MAXN], nl=1, nr;	
/*********************\
注意这里
\*********************/
LL ans[MAXN], now, cnt[MAXN];

struct ques{
	int l, r, id;
	friend bool operator < (ques a, ques b)
	{
		return pos[a.l]^pos[b.l] ? pos[a.l]<pos[b.l] : (pos[a.l]&1 ? a.r<b.r : a.r>b.r);
	} 
}q[MAXN];

il void add(int i)
{
	now += (cnt[a[i]] << 1) + 1ll;
	++cnt[a[i]];
}

il void del(int i)
{
	now -= (cnt[a[i]] << 1) - 1ll;
	--cnt[a[i]];
}

int main()
{
	freopen("P2709_1.in", "r", stdin);
	freopen("P2709myout.out", "w", stdout);
	init(n); init(m); init(k);
	rtn = sqrt(n);
	for(rg int i=1, top=(n+rtn-1)/rtn ; i<=top ; i++)
		for(rg int j=(i-1)*rtn+1 ; j<=i*rtn ; j++)
			pos[j] = i;
	for(rg int i=1 ; i<=n ; i++)
		init(a[i]);
		
	for(rg int i=1 ; i<=m ; i++)
	{
		init(q[i].l);
		init(q[i].r);
		q[i].id = i;
	}
	
	sort(q+1, q+m+1);
	
	for(rg int i=1 ; i<=m ; i++)
	{
		int ql = q[i].l, qr = q[i].r;
		while(qr < nr)	del(nr--);	
		while(qr > nr)	add(++nr);
		while(ql > nl)	del(nl++);
		while(ql < nl)	add(--nl);
		ans[q[i].id] = now;
	}
	
	for(rg int i=1 ; i<=m ; i++)
		printf("%lld\n", ans[i]);
	
	return 0;
}

代码2：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define rg register
#define il inline
#define MAXN 50010
#define LL long long
using namespace std;

il void init(int &x)
{
	x = 0;
	char c = getchar();
	while(c>'9' || c<'0')	c = getchar();
	while(c>='0' && c<='9')
	{
		x = (x<<1) + (x<<3) +(c^48);
		c = getchar();
	}
}

int n, m, k, rtn, pos[MAXN], a[MAXN], nl=1, nr;
/*********************\
注意这里
\*********************/
LL ans[MAXN], now, cnt[MAXN];

struct ques{
	int l, r, id;
	friend bool operator < (ques a, ques b)
	{
		return pos[a.l]^pos[b.l] ? pos[a.l]<pos[b.l] : (pos[a.l]&1 ? a.r<b.r : a.r>b.r);
	} 
}q[MAXN];

il void add(int i)
{
	now += (cnt[a[i]] << 1) + 1ll;
	++cnt[a[i]];
}

il void del(int i)
{
	now -= (cnt[a[i]] << 1) - 1ll;
	--cnt[a[i]];
}

int main()
{
	freopen("P2709_1.in", "r", stdin);
	freopen("P2709myout.out", "w", stdout);
	init(n); init(m); init(k);
	rtn = sqrt(n);
	for(rg int i=1, top=(n+rtn-1)/rtn ; i<=top ; i++)
		for(rg int j=(i-1)*rtn+1 ; j<=i*rtn ; j++)
			pos[j] = i;
	for(rg int i=1 ; i<=n ; i++)
		init(a[i]);
		
	for(rg int i=1 ; i<=m ; i++)
	{
		init(q[i].l);
		init(q[i].r);
		q[i].id = i;
	}
	
	sort(q+1, q+m+1);
	
	for(rg int i=1 ; i<=m ; i++)
	{
		int ql = q[i].l, qr = q[i].r;
		while(qr < nr)	del(nr--);	
		while(qr > nr)	add(++nr);
		while(ql > nl)	del(nl++);
		while(ql < nl)	add(--nl);
		ans[q[i].id] = now;
	}
	
	for(rg int i=1 ; i<=m ; i++)
		printf("%lld\n", ans[i]);
	
	return 0;
}

大概除了顺序一模一样吧..