小Z的袜子

洛谷
暴力分块
玄学排序
注意规律
后面答案是除一下（gcd）就没了
还有特判0&&（l==r）

#include<bits/stdc++.h>
#define re return
#define ll long long
#define inc(i,l,r) for(register int i=l;i<=r;++i)
#define dec(i,l,r) for(register int i=l;i>=r;--i)
const int maxn=50005,maxm=50005; 

using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}
ll n,m,pos[maxn],c[maxn];
ll s[maxn],ans;
struct node{
    ll l,r,id;
    ll a,b;
}a[maxn];
bool cmp(node a,node b)
{
    if(pos[b.l]==pos[a.l])re a.r<b.r;
    else re a.l<b.l;    
}
bool cmp1(node x,node y){re x.id<y.id;}

inline void modify(ll x,ll add)
{
    ans-=s[c[x]]*s[c[x]];
    s[c[x]]+=add;
    ans+=s[c[x]]*s[c[x]];
}

inline ll gcd(ll a,ll b){re b?gcd(b,a%b):a;}
int main()
{

    rd(n),rd(m);
    inc(i,1,n)rd(c[i]);
    ll block=sqrt(n);
    inc(i,1,n)pos[i]=(i-1)/block+1;
    inc(i,1,m){
        rd(a[i].l),rd(a[i].r);
        a[i].id=i;
    }
    sort(a+1,a+m+1,cmp);
    ll l=1,r=0;
    inc(i,1,m)
    {
        while(r<a[i].r)modify(r+1,1),++r;
        while(a[i].r<r)modify(r,-1),--r;
        while(l<a[i].l)modify(l,-1),++l;
        while(l>a[i].l)modify(l-1,1),--l;
        if(a[i].l==a[i].r)
        {
            a[i].a=0;
            a[i].b=1;
            continue;
        }
        a[i].a=ans-(a[i].r-a[i].l+1);
        //modify=>ans-=s[c[x]]*(s[c[x]]-1)
        a[i].b=(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
        ll g=gcd(a[i].a,a[i].b);
        a[i].a/=g;
        a[i].b/=g;
        if(!a[i].a)a[i].b=1;
    }
    
    sort(a+1,a+m+1,cmp1);
    inc(i,1,m)
    printf("%lld/%lld\n",a[i].a,a[i].b);
}

小Z的袜子

原文：https://www.cnblogs.com/lsyyy/p/11273203.html