洛谷P1494 [国家集训队]小Z的袜子（莫队）

 

从总的袜子数中任意选取 2 个作为分母，再从任意颜色相同的袜子数中选取 2 个，可以先与处理一下   ，这样每次更新减去上一次的值，在加上这一次的值。

虽然数据量不大，但是预处理的时候会爆 int ，累加答案的时候也会爆，所以采用 long long 

const int N=5e4+5;

    int i,j,k;
    int n,m,t;
    int a[N];
    int num,block,bel[N];
    struct Node
    {
        int id;
        int l,r;
        bool operator<(Node b)
        {
            return bel[l]^bel[b.l] ? l<b.l : (bel[l]&1 ? r<b.r : r>b.r); 
        }
    }q[N];
    ll cnt[N],cur;
    pll ans[N];

ll jc[N];
void init()
{
    jc[0]=jc[1]=0;
    for(ll i=2;i<N;i++) jc[i]=(i-1)*i/2;
}

void build()
{
    block=sqrt(n);
    num=n/block; if(n%block) num++;
    for(int i=1;i<=num;i++){
        int l=block*(i-1)+1;
        int r=min(block*i,n);
        for(int j=l;j<=r;j++) bel[j]=i;
    }
}

void add(int pos)
{
    int x=a[pos];
    cur-=jc[cnt[x]];
    cnt[x]++;
    cur+=jc[cnt[x]];
}

void del(int pos)
{
    int x=a[pos];
    cur-=jc[cnt[x]];
    cnt[x]--;
    cur+=jc[cnt[x]];
}

int main()
{
    //IOS;
    init();
    while(~sdd(n,m)){
        for(int i=1;i<=n;i++) sd(a[i]);
        for(int i=1;i<=m;i++) sdd(q[i].l,q[i].r),q[i].id=i;
        build(); sort(q+1,q+1+m);
        int l=1,r=0; cur=0;
        for(int i=1;i<=m;i++){
            while(l>q[i].l) add(--l);
            while(l<q[i].l) del(l++);
            while(r>q[i].r) del(r--);
            while(r<q[i].r) add(++r);
            ans[q[i].id].fr=cur;
            ans[q[i].id].sc=jc[r-l+1];
        }
        for(int i=1;i<=m;i++){
            ll d=__gcd(ans[i].fr,ans[i].sc);
            //dbg(ans[i].fr);
            if(d==0) printf("0/1\n");
            else printf("%lld/%lld\n",ans[i].fr/d,ans[i].sc/d);
        }
    }
    //PAUSE;
    return 0;
}