小Z

枫林晚 · 2018-05-11 22:02:02 · 个人记录

#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)
                {

                }
            }
        }
    }
}