bzoj 2038 小z的袜子 莫队

莫队大法好，入坑保平安

只要能O(1)或O(log)转移，离线莫队貌似真的无敌。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define N 50005

using namespace std;

int n,m,nn,tot,c[N],be[N],num[N];

struct Query{

	int id,l,r;

	long long son,mom;

}qr[N];

bool cmp(Query a,Query b){

	if(be[a.l]==be[b.l]&&a.r==b.r)

		return a.l<b.l;

	if(be[a.l]==be[b.l]) return a.r<b.r;

	return be[a.l]<be[b.l];

}

bool com(Query a,Query b){

	return a.id<b.id;

}

long long ans;

void work(int x,int y){

	ans-=num[c[x]]*num[c[x]];

	num[c[x]]+=y;

	ans+=num[c[x]]*num[c[x]];

}

long long gcd(long long x,long long y){

	return y==0?x:gcd(y,x%y);

}

int main()

{

	scanf("%d%d",&n,&m);

	nn=(int)sqrt(n);

	for(int i=1;i<=n;i++){

		scanf("%d",&c[i]);

		be[i]=(i-1)/nn+1;

	} tot=be[n];

	for(int i=1;i<=m;i++){

		qr[i].id=i;

		scanf("%d%d",&qr[i].l,&qr[i].r);

	}

	sort(qr+1,qr+m+1,cmp);

	int l=1,r=0;

	for(int i=1;i<=m;i++){

		qr[i].mom=(long long)(qr[i].r-qr[i].l+1)*(qr[i].r-qr[i].l);

		while(l<qr[i].l) work(l++,-1);

		while(l>qr[i].l) work(--l,1);

		while(r<qr[i].r) work(++r,1);

		while(r>qr[i].r) work(r--,-1);

		qr[i].son=(long long)ans-(qr[i].r-qr[i].l+1);

		if(qr[i].son==0) qr[i].mom=1;

		else{

			long long gg=gcd(qr[i].son,qr[i].mom);

			qr[i].son/=gg; qr[i].mom/=gg;

		}

	}

	sort(qr+1,qr+m+1,com);

	for(int i=1;i<=m;i++)

		printf("%lld/%lld\n",qr[i].son,qr[i].mom);

	return 0;

}