Submission #29888994

---

Source Code Expand

/*
他决定要“格”院子里的竹子。于是他搬了一条凳子坐在院子里，面对着竹子硬想了七天，结果因为头痛而宣告失败。
DONT NEVER AROUND . //
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read()
{
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(int x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
const int B=2000;
int bel[100005];
struct Query{
	int l,r,id;
	Query(int L=0,int R=0,int I=0){l=L,r=R,id=I;}
	bool operator < (Query ano) const
	{
		if(bel[l]==bel[ano.l])	return r<ano.r;
		return bel[l]<bel[ano.l];
	}
}que[1000005];
int n,q,a[100005],gr,ans[1000005],app[100005];
void Add(int x)
{
	gr-=app[a[x]]/2;
	++app[a[x]];
	gr+=app[a[x]]/2;
}
void Sub(int x)
{
	gr-=app[a[x]]/2;
	--app[a[x]];
	gr+=app[a[x]]/2;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)	a[i]=read();
	for(int i=1;i<=n;++i)	bel[i]=(i-1)/B+1;
	q=read();
	for(int i=1;i<=q;++i)
	{
		int l=read(),r=read();
		que[i]=Query(l,r,i);
	}
	sort(que+1,que+1+q);
	for(int i=1,l=1,r=0;i<=q;++i)
	{
		while(r<que[i].r)	Add(++r);
		while(r>que[i].r)	Sub(r--);
		while(l<que[i].l)	Sub(l++);
		while(l>que[i].l)	Add(--l);
		ans[que[i].id]=gr;
	}
	for(int i=1;i<=q;++i)	write(ans[i]),puts("");
	return 0;
}

Submission Info

Judge Result