BZOJ2038 – [2009国家集训队]小Z的袜子(hose)(在线分块||离线莫队算法)

BZOJ2038

【分析】和HDU5286基本一样，可以使用在线的分块算法；分块预处理每一块作为起点到n位置的所有不同数的C(cnt[i],2)之和，以及第0~i块每个颜色的前缀和；而C(n,2)就是n*(n-1)/2，对于C(n,2)可以得到递推式：C(N,2) = C(N-1,2)+N-1；这样就能算出每次加入一个数字的sum变化;这样对于查询[l,r]中间的连续块只要先把答案加上以连续块的答案，然后对应于左边和右边的两个不完整快只需要一个一个加入计算即可。复杂度n*sqrt(n)*2;然而常数有点大和暴力都差不多时间了。

所以学了神奇的莫队算法，其实说白了就一句话：分块+离线按询问左端点所在块以及右端点升序排序；

对于上一次查询区间[a,b]和这次需要查询的区间[c,d];如果a<c则删除区间(a,c]，否则加上区间[c,a);如果b<d则加上区间[b,d),否则删除区间(d,b];可以证明复杂度是N*sqrt(n)的；

【AC CODE(在线分块)】3384ms

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10,SIZE = 200,BLOCK = MAXN/SIZE+10;
int a[MAXN],n,sn,all;
LL sum[BLOCK][MAXN],cnt[BLOCK][MAXN],tmp[MAXN],tnum[MAXN];

LL g(LL x) {return x*(x-1)/2;}
LL gcd(LL a, LL b)
{
	while(b)
	{
		a %= b;
		if(a < b) swap(a,b);
	}
	return a;
}
LL ans;
void cal(int x, int y, int st, int ed)
{
	repe(i,x,y)
	{
		if(!tmp[a[i]])
			tnum[all++] = a[i],tmp[a[i]] = cnt[ed][a[i]]-cnt[st+1][a[i]];
		ans += (tmp[a[i]]++);
	}
}
LL query(int x, int y)
{
	int st = x/SIZE,ed = y/SIZE;
	if(st == ed)
	{
		ans = all = 0;
		cal(x,y,0,1);
		rep(i,0,all) tmp[tnum[i]] = 0;
		return ans;
	}
	if(st+1 == ed)
	{
		ans = all = 0;
		cal(x,(st+1)*SIZE-1,0,1);
		cal(ed*SIZE,y,0,1);
		rep(i,0,all) tmp[tnum[i]] = 0;
		return ans;
	}
	ans = sum[st+1][ed*SIZE-1];
	all = 0;
	cal(x,(st+1)*SIZE-1,st,ed);
	cal(ed*SIZE,y,st,ed);
	rep(i,0,all) tmp[tnum[i]] = 0;
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int q;
	scanf("%d %d", &n, &q);
	rep(i,0,n) scanf("%d", &a[i]);
	sn = n/SIZE+(bool)(n%SIZE);
	rep(i,0,sn)
	{
		tmp[a[i*SIZE]]++;
		rep(j,i*SIZE+1,n) sum[i][j] = sum[i][j-1]+(tmp[a[j]]++);
		clc(tmp,0);
	}
	rep(i,0,sn)
	{
		int st = i*SIZE,ed = min(n,(i+1)*SIZE);
		memcpy(cnt[i+1],cnt[i],sizeof(cnt[i]));
		rep(j,st,ed) cnt[i+1][a[j]]++;
	}
	while(q--)
	{
		int x,y;
		scanf("%d %d", &x, &y);
		LL m = query(x-1,y-1),d = g(y-x+1);
		LL g = gcd(m,d);
		printf("%u/%u\n",m/g,d/g);
	}
	return 0;
}

【AC CODE(离线莫队)】484ms

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10,SIZE = 500;
struct NODE{
	LL x,y;
	int id,block;
	bool operator<(const NODE&t)const{
		if(block != t.block) return block < t.block;
		return y < t.y;
	}
}in[MAXN];
int a[MAXN];
LL ans1[MAXN],ans2[MAXN],cnt[MAXN];

LL gcd(LL a, LL b)
{
	while(b)
	{
		a %= b;
		if(a < b) swap(a,b);
	}
	return a;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,q;
	scanf("%d %d", &n, &q);
	rep(i,0,n) scanf("%d", &a[i]);
	rep(i,0,q)
	{
		scanf("%d %d", &in[i].x, &in[i].y);
		in[i].x--;in[i].y--;
		in[i].id = i,in[i].block = in[i].x/SIZE;
	}
	sort(in,in+q);
	LL sum = 0,x = 0,y = 0;cnt[a[0]]++;
	rep(i,0,q)
	{
		while(x < in[i].x)
		{
			sum -= (--cnt[a[x++]]);
		}
		while(x > in[i].x)
		{
			sum += (cnt[a[--x]]++);
		}
		while(y < in[i].y)
		{
			sum += (cnt[a[++y]]++);
		}
		while(y > in[i].y)
		{
			sum -= (--cnt[a[y--]]);
		}
		LL d = (y-x+1)*(y-x)/2;
		LL g = gcd(sum,d);
		ans1[in[i].id] = sum/g;ans2[in[i].id] = d/g;
	}
	rep(i,0,q) printf("%u/%u\n", ans1[i],ans2[i]);
	return 0;
}