「国家集训队」小Z的袜子

时间：2021-08-02 06:52:31

「国家集训队」小Z的袜子

传送门

莫队板子题。

注意计算答案的时候，由于分子分母都要除以2，所以可以直接约掉，这样在开桶算的时候也方便一些。

参考代码：

#include <algorithm>

#include <cstdio>

#include <cmath>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define int long long

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 50010;

int n, gap, m, c[_], pos[_], s[_], ans;

struct Ask { int l, r, id; } ask[_];

struct Ans { int a, b; } res[_];

inline bool cmp(const Ask& x, const Ask& y)

{ return pos[x.l] == pos[y.l] ? x.r < y.r : x.l < y.l; }

inline void update(int x, int v)

{ ans -= s[c[x]] * s[c[x]], s[c[x]] += v, ans += s[c[x]] * s[c[x]]; }

signed main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	read(n), read(m), gap = sqrt(1.0 * n);

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

		read(c[i]), pos[i] = (i - 1) / gap + 1;

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

		read(ask[i].l), read(ask[i].r), ask[i].id = i;

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

	for (rg int i = 1, l = 1, r = 0; i <= m; ++i) {

		while (l < ask[i].l) update(l++, -1);

		while (l > ask[i].l) update(--l, 1);

		while (r < ask[i].r) update(++r, 1);

		while (r > ask[i].r) update(r--, -1);

		int now = ask[i].id;

		if (ask[i].l == ask[i].r) { res[now].a = 0, res[now].b = 1; continue; }

		res[now].a = ans - (ask[i].r - ask[i].l + 1);

		res[now].b = 1ll * (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l);

		int g = __gcd(res[now].a, res[now].b);

		res[now].a /= g, res[now].b /= g;

	}

	for (rg int i = 1; i <= m; ++i) printf("%lld/%lld\n", res[i].a, res[i].b);

	return 0;

}

相关文章