大佬较为详细的莫队复杂度证明

普通莫队

小z的袜子

前面统计推一波式子

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
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; 
}

const int maxn=5e4+5;

int n,m,pos[maxn],cnt[maxn],c[maxn],tot;

struct node{
    int l,r,id,ans;
    inline bool operator<(node a)
    {
        re (pos[l]^pos[a.l])?pos[l]<pos[a.l]:(pos[l]&1?r<a.r:r>a.r);
    }
}q[maxn];

inline bool cmp(node a,node b)
{
    re a.id<b.id;
}

inline void add(int x)
{
    tot+=(cnt[x]<<1);
    ++cnt[x];
}

inline void del(int x)
{
    --cnt[x];
    tot-=(cnt[x]<<1);
}

#define ll long long

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


int main()
{
//  freopen("in.txt","r",stdin);
    rd(n);
    rd(m);
    int len=n/(int)sqrt(n);
    inc(i,1,n)
    {
        rd(c[i]);
        pos[i]=(i-1)/len+1;
    }   
    inc(i,1,m)
    rd(q[i].l),rd(q[i].r),q[i].id=i;

    sort(q+1,q+m+1);
    int l=1,r=0;

    inc(i,1,m)
    {
//注意要先移动r，再移动l，避免统计时出错
        while(r<q[i].r)add(c[++r]);
        while(r>q[i].r)del(c[r--]);
        while(l<q[i].l)del(c[l++]);
        while(l>q[i].l)add(c[--l]);
        q[i].ans=tot;
    }

    sort(q+1,q+m+1,cmp);
    inc(i,1,m)
    if(!q[i].ans)
    printf("0/1\n");
    else 
    {
        ll Y=q[i].ans,X=q[i].r-q[i].l+1;
        X*=(X-1);
        ll d=gcd(Y,X);
        printf("%lld/%lld\n",Y/d,X/d);
    }
    re 0;
}

View Code