bzoj2038小z的袜子

用平面曼哈顿距离最小生成树或者莫队算法都可以吖QwQ~

然而显然后者更好写（逃~）

莫队怎么写就看图吧QwQ~

话说我一开始没开long long然后拍了3000组没拍出错交上去Wa了QAQ

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int Mx=50010;
struct Node { int l,r,num; } que[Mx];
bool cmp1 (Node a,Node b) { return a.l<b.l; }
bool cmp2 (Node a,Node b) { return a.r<b.r; }
int n,m,c[Mx],num[Mx],ans[Mx],ans1[Mx][2];
inline int gcd (int a,int b) { int tmp; while(a>0) tmp=b%a,b=a,a=tmp;  return b; }
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<=m;i++) { scanf("%lld%lld",&que[i].l,&que[i].r);if(que[i].l>que[i].r) swap(que[i].l,que[i].r); }
    for(int i=1;i<=m;i++) que[i].num=i;
    sort(que+1,que+1+m,cmp1);
    for(int i=1;i<=m;i+=sqrt(m)) sort(que+i,que+min(m,i+(int)sqrt(m)),cmp2);
    for(int i=1;i<=m;i++)
    {
        if(i%(int)sqrt(m)==1||i==1)
        {
            memset(num,0,sizeof(num));
            for(int j=que[i].l;j<=que[i].r;j++) num[c[j]]++;
            for(int j=0;j<=n;j++) ans[i]+=num[j]*(num[j]-1)/2;
        }
        else
        {
            for(int j=que[i-1].l,to=que[i].l;j!=to;)
            {
                if(j<to) ans[i]-=num[c[j]]-1,num[c[j]]--,j++;
                else ans[i]+=num[c[j-1]],num[c[j-1]]++,j--;
            }
            for(int j=que[i-1].r,to=que[i].r;j!=to;)
            {
                if(j<to) ans[i]+=num[c[j+1]],num[c[j+1]]++,j++;
                else ans[i]-=num[c[j]]-1,num[c[j]]--,j--;
            }
            ans[i]+=ans[i-1];
        }    
        int div=gcd(ans[i],(que[i].r-que[i].l+1)*(que[i].r-que[i].l)/2);
        if(que[i].r==que[i].l||ans[i]==0) ans1[que[i].num][0]=0,ans1[que[i].num][1]=1;
        else ans1[que[i].num][0]=ans[i]/div,ans1[que[i].num][1]=(que[i].r-que[i].l+1)*(que[i].r-que[i].l)/(div*2);
    }
    for(int i=1;i<=m;i++) printf("%lld/%lld
",ans1[i][0],ans1[i][1]);
    return 0;
}