Bzoj2038/洛谷P1494 小Z的袜子（莫队）

题面

题解

考虑莫队算法，首先对询问进行分块（分块大小为$sqrt(n)$），对于同一个块内的询问，按照左端点为第一关键字，右端点为第二关键字排序。我们统计这个区间内相同的颜色有多少个，假设某种颜色$i$有$j$个，则贡献就是$j\times(j-1)$，最后记得化成既约分数。

#include <set>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::swap; using std::sort;

typedef long long ll;

using std::set;

template<typename T>

void read(T &x) {

	int flag = 1; x = 0; char ch = getchar();

	while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 5e4 + 10, M = 5e4 + 10;

int n, m, c[N], siz, blo, t, l, r, v[N];

struct Ques { int x, y, z; } q[M], b[M];

inline bool cmp1 (Ques a, Ques b) { return a.x < b.x; }

inline bool cmp2 (Ques a, Ques b) { return a.y < b.y; }

ll up[M], down[M], _gcd, tmp;

template<typename T>

T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

void modify (int st, int ed, int flag) {

	for(int i = st; i < ed; ++i) {

		tmp -= 1ll * v[c[i]] * (v[c[i]] - 1);

		v[c[i]] += flag;

		tmp += 1ll * v[c[i]] * (v[c[i]] - 1);

	}

}

int main () {

#ifdef OFFLINE_JUDGE

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

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

#endif

	read(n), read(m);

	for(int i = 1; i <= n; ++i) read(c[i]);

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

		read(q[i].x), read(q[i].y), q[i].z = i;

	sort(&q[1], &q[m + 1], cmp1);

	siz = sqrt(n), blo = (n / siz) + (n % siz != 0);

	for(int i = 0, j = 1; i < blo; ++i) {

		t = 0;

		while(j <= m && q[j].x > i * siz && q[j].x <= (i + 1) * siz) b[++t] = q[j++];

		sort(&b[1], &b[t + 1], cmp2);

		l = b[1].x, r = b[1].x - 1, tmp = 0;

		memset(v, 0, sizeof v);

		for(int k = 1; k <= t; ++k) {

			if(b[k].x == b[k].y) {

				up[b[k].z] = 0, down[b[k].z] = 1;

				continue;

			}

			if(l < b[k].x) modify(l, b[k].x, -1);

			else if(l > b[k].x) modify(b[k].x, l, 1);

			if(r < b[k].y) modify(r + 1, b[k].y + 1, 1);

			else if(r > b[k].y) modify(b[k].y + 1, r + 1, -1);

			up[b[k].z] = tmp, down[b[k].z] = b[k].y - b[k].x + 1;

			l = b[k].x, r = b[k].y;

		}

	}

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

		if(!down[i] || !up[i]) { puts("0/1"); continue; }

		down[i] = down[i] * (down[i] - 1);

		tmp = gcd(up[i], down[i]);

		printf("%lld/%lld\n", up[i] / tmp, down[i] / tmp);

	}

	return 0;

}

巴特西

Bzoj2038/洛谷P1494 小Z的袜子（莫队）

题面

题解

最新文章

热门文章