莫队算法 sqrt(n)分块思想

在此说一下本渣对莫队算法思想的一些浅薄理解

莫队算法的思想就是对真个区间的分块,然后按照每块来分别进行计算,这样最终的复杂度可以达到n*sqrt(n)

小Z的袜子是一道非常经典的题目.:题目链接http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29469#problem/A

我们先对整个区间分块,然后按照左区间所在的块进行排序,如果左区间在相同的块内,则按照右区间进行排序.

如此相当于对每个左区间在相同块内的询问,我们只要右区间从最小迭代到最大即可.也就是说我们把算法的复杂度的锅让区间的左端点来背 = =,恩......

当然了,既然使用如上算法,那么显然我们要进行离线处理.

具体代码如下:

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstring>

#include <cmath>

#include <set>

using namespace std;

int n, m, a[100010], num[100010], unit;

struct N {			//存询问的信息

	int l, r, id;

	bool operator < (const N &rhs) const {		//先按照左端点是否所在块进行排序,然后按照右端点排序

		if (l / unit == rhs.l / unit) return r < rhs.r;

		else return l / unit < rhs.l / unit;

	}

} q[100010];

pair<long long, long long>ans[100010];			//储存答案

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

	if (y == 0) return x;

	return gcd(y, x % y);

}

int main() {

	//freopen("in.in", "r", stdin);

	//freopen("out.out", "w", stdout);

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

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

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

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

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

		q[i].id = i;

	}

	unit = sqrt(n);

	sort(q, q + m);

	int l = 1,r = 0;

	long long tmp = 0;

	memset(num,0,sizeof(num));

	for(int i=0;i<m;i++){			//迭代求答案过程

		while(r < q[i].r){

			r++;

			tmp -= (long long)num[a[r]] * (num[a[r]] - 1);

			num[a[r]]++;

			tmp += (long long)num[a[r]] * (num[a[r]] - 1);

		}

		while(r > q[i].r){

			tmp -= (long long)num[a[r]] * (num[a[r]] - 1);

			num[a[r]]--;

			tmp += (long long)num[a[r]] * (num[a[r]] - 1);

			r--;

		}

		while(l < q[i].l){

			tmp -= (long long)num[a[l]] * (num[a[l]] - 1);

			num[a[l]]--;

			tmp += (long long)num[a[l]] * (num[a[l]] - 1);

			l++;

		}

		while(l > q[i].l){

			l--;

			tmp -= (long long)num[a[l]] * (num[a[l]] - 1);

			num[a[l]]++;

			tmp += (long long)num[a[l]] * (num[a[l]] - 1);

		}

		ans[q[i].id].first  = tmp;

		ans[q[i].id].second = (long long)(q[i].r - q[i].l + 1) * (q[i].r - q[i].l);

	}

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

		if(ans[i].first + ans[i].second == 0) { printf("0/1\n"); continue; }

		long long tmp = gcd(ans[i].second,ans[i].first);

		printf("%lld/%lld\n",ans[i].first/tmp,ans[i].second/tmp);

	}

	return 0;

}

巴特西

莫队算法 sqrt(n)分块思想

最新文章

热门文章