[2009国家集训队]小Z的袜子(hose)

题目

bzoj2038

题解

网上题解很多，蒟蒻就不掺和了，这里贴一个写的不错的
清橙A1206 小Z的袜子(莫队算法)

我代码差不多也是照着Ta写的，加了一些注释

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 50005
#define ll long long 
using namespace std;

int n,m,c[N]; 
int block,blo[N];
ll up[N],down[N];
ll ans,sum[N];//sum[i]记录当前区间颜色i的个数 

struct node
{
	int l,r,id;
}q[N];

bool cmp(node x,node y)
{
	if(blo[x.l]==blo[y.l]) return x.r<y.r;
	return blo[x.l]<blo[y.l];
}

ll gcd(ll a,ll b)
{
	if(!b) return a;
	return gcd(b,a%b);
}

void update(int r,int deta)
{
	ans-=sum[c[r]]*sum[c[r]];
	sum[c[r]]+=deta;
	ans+=sum[c[r]]*sum[c[r]];
}

int main()
{
	scanf("%d%d",&n,&m);block=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]),blo[i]=(i-1)/block+1;
	for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	int pr=0,pl=1;//记录上一次计算的区间 
	for(int i=1;i<=m;i++)
	{
		int id=q[i].id;
		if(q[i].l==q[i].r)//如果只有一只袜子 
		{
			up[id]=0;down[id]=1;
			continue;
		}
		if(q[i].r>pr)//右端有部分区间没被计算 
			for(int j=pr+1;j<=q[i].r;j++) update(j,1);//逐一扩大区间范围 
		else //右端计算了多余区间 
			for(int j=pr;j>q[i].r;j--) update(j,-1);  //逐一缩小区间范围
		pr=q[i].r;//记录区间右端点 
		//接下来是对左端点进行调整
		if(q[i].l>pl)
			for(int j=pl;j<q[i].l;j++) update(j,-1);
		else
			for(int j=pl-1;j>=q[i].l;j--) update(j,1); 
		pl=q[i].l;
		ll up_=ans-(q[i].r-q[i].l+1)*1;//因为两次选的不能是同一只袜子，ans减去两次选择相同的情况 
		ll down_=(ll)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
		ll g=gcd(up_,down_);//约分 
		up[id]=up_/g;down[id]=down_/g;
	}
	for(int i=1;i<=m;i++) printf("%lld/%lld
",up[i],down[i]);
	return 0;
}