小Z的襪子

簡單莫隊

對襪子分塊，對操作排序

機率是 某顔色個數/總個數

然後暴力修改就行了

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm> 
#define ll long long
using namespace std;
const int M=;int cnt[M],Id[M],c[M],L,R,n,m,block;ll x,y,GCD,ansx[M],ansy[M];
struct node{int l,id,r;bool operator <(node b)const{return (Id[l]==Id[b.l])?(r<b.r):(Id[l]<Id[b.l]);}}a[M];
void add(int t){if(cnt[t]) x+=*cnt[t];cnt[t]++;}
void del(int t){if(--cnt[t]) x-=*cnt[t];}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} 
int main(){
    scanf("%d%d",&n,&m);int block=sqrt(m);
    for(int i=;i<=n;i++) scanf("%d",&c[i]),Id[i]=(i-)/block+;
    for(int i=;i<=m;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
    sort(a+,a+m+);L=a[].l,R=a[].r;
    for(int i=L;i<=R;i++)add(c[i]);y=l*(R-L+)*(R-L);
    if(x)GCD=gcd(x,y),ansx[a[].id]=x/GCD,ansy[a[].id]=y/GCD;
    else ansx[a[].id]=,ansy[a[].id]=;
    for(int i=;i<=m;i++){int l=a[i].l,r=a[i].r;y=l*(r-l+)*(r-l);
        while(L>l) add(c[--L]);while(L<l) del(c[L++]);
        while(R>r) del(c[R--]);while(R<r) add(c[++R]);
        if(x)GCD=gcd(x,y),ansx[a[i].id]=x/GCD,ansy[a[i].id]=y/GCD;
        else ansx[a[i].id]=,ansy[a[i].id]=;
    }
    for(int i=;i<=m;i++) printf("%lld/%lld\n",ansx[i],ansy[i]);
}