小Z
枫林晚
2018-05-11 22:02:02
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=50000+10;
int n,m;
struct node{
int l,r;
int hao;
bool friend operator <(node a,node b)
{
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
}q[N];
int ans[N][2];
int a[N];
int cnt[N];
int sum;
int L,R;
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].hao=i;
sort(q+1,q+m+1);
for(int i=1;i<=m;i++)
{
if(i==1){
L=q[i].l,R=q[i].r;
sum=0;
for(int j=q[i].l;j<=q[i].r;j++)
{
cnt[a[j]]++;
}
for(int i=1;i<=n;i++)
if(cnt[i]) sum+=cnt[i]*cnt[i];
sum=sum-(q[i].r-q[i].l+1);
ans[q[i].hao][0]=sum;
ans[q[i].hao][1]=(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
}
else{//duo 1 : sum+ 2*cnt[a[j]]
//shao 1: sum- 2*cnt[a[j]]+2
if(R<q[i].r)
{
}
else if(R>q[i].r)
{
}
if(L<q[i].l)
{
while(L<q[i].l)
{
}
}
}
}
}
```