特辑：莫队

题目按难易度为关键字升序排列。

Problem L:小B的询问

莫队板子题，秒了

#include <bits/stdc++.h>

int n, m, k, a[50005], pos[50005], cnt[50005];
long long ans[50005], tmp;

inline int R() {
	int a = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
	return a;
}

struct Block {
	int l, r, id;
	friend bool operator <(Block a, Block b) {
		if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
		if (pos[a.l] & 1) return a.r < b.r;
		else return a.r > b.r;
	}
} ask[50005];

inline void Add(int x) {
	tmp += 2 * cnt[a[x]] + 1, ++cnt[a[x]];
}

inline void Del(int x) {
	tmp += -2 * cnt[a[x]] + 1, --cnt[a[x]];
}

signed main() {
	n = R(), m = R(), k = R();
	for (int i = 1; i <= n; i++) a[i] = R();
	int blk = pow(n, 0.55);
	for (int i = 1; i <= n; i++)
		pos[i] = (i - 1) / blk + 1;
	for (int i = 1; i <= m; i++) ask[i].l = R(), ask[i].r = R(), ask[i].id = i;
	std::sort(ask + 1, ask + 1 + m);
	for (int i = 1, l = 1, r = 0; i <= m; i++) {
		while (l > ask[i].l) Add(--l);
		while (l < ask[i].l) Del(l++);
		while (r < ask[i].r) Add(++r);
		while (r > ask[i].r) Del(r--);
		ans[ask[i].id] = tmp;
	}
	for (int i = 1; i <= m; i++)
		printf("%lld
", ans[i]);
	return 0;
}

Problem M: 小Z的袜子

分母部分为选两只袜子总方案数 $ C_{R-L+1} ^ 2 $.

分子部分为每种颜色袜子选两次方案数 (sum C_{cnt_i}^2).

所以答案为 (frac{sum C_{cnt_i}^2}{C_{R-L+1} ^ 2} = frac{sum cnt_i^2 - sum cnt_i}{(R-L+1)(R-L)})

转移显然了，懒得写

Add:

#include <bits/stdc++.h>
#define ll long long

const int N = 50000 + 233;
int n, m;
ll pos[N], block, cnt[N], ans[N], c[N], above[N], below[N], tmp;
bool zero[N];

struct Node {
	int l, r, id;
	friend bool operator <(Node a, Node b) {
		if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
		else if (pos[a.l] & 1) return a.r < b.r;
		else return a.r > b.r;
	}
} nd[N];

inline ll R() {
	int a = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
	return a;
}

ll gcd(ll x, ll y) {
	return y == 0 ? x : gcd(y, x % y);
}

inline void Add(ll x) {
	tmp += 2 * cnt[c[x]] + 1, ++cnt[c[x]];
}

inline void Del(ll x) {
	tmp -= 2 * cnt[c[x]] - 1, --cnt[c[x]];
}

void print(ll x, ll y) {
	x -= y, y = y * (y - 1);
	ll g = gcd(x, y);
	printf("%lld/%lld
", x / g, y / g);
}

signed main() {
	n = R(), m = R();
	for (int i = 1; i <= n; i++) 
		c[i] = R();
	for (int i = 1; i <= m; i++)
		nd[i].l = R(), nd[i].r = R(), nd[i].id = i;
	block = pow(n, 0.55);
	for (int i = 1; i <= n; i++)
		pos[i] = (i - 1) / block + 1;
	std::sort(nd + 1, nd + 1 + m);
	for (int i = 1, l = 1, r = 0; i <= m; i++) {
		int L = nd[i].l, R = nd[i].r, id = nd[i].id;
		if (L == R) {
			zero[id] = 1;
			continue;
		}
		while (l > L) Add(--l);
		while (l < L) Del(l++);
		while (r < R) Add(++r);
		while (r > R) Del(r--);
		above[id] = tmp, below[nd[i].id] = R - L + 1;
	}
	for (int i = 1; i <= m; i++) {
		if (zero[i]) puts("0/1");
		else print(above[i], below[i]);
	}
	return 0;
}

Problem K: 作业

直接莫队把每种数的出现次数和种类维护了。

难点在统计，很多人写了树状数组，其实复杂度多了个log，是不对的，放在时限小的OJ（比如Luogu）就直接凉了

正解应该对值域分块，(O(N sqrt N))解决。

如果你会CDQ分治那不是更好吗

数组开小WA了4次，丢人（

#include <bits/stdc++.h>

const int N = 2000000 + 233;
int n, m, a[N], block, pos[N], cnt[N], ans_1[N], ans_2[N], L[N], f[N], g[N];

struct Node {
	int l, r, a, b, id;
	friend bool operator <(Node a, Node b) {
		if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
		else if (pos[a.l] & 1) return a.r < b.r;
		else return a.r > b.r;
	} 
} nd[N];

inline int R() {
	int a = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
	return a;
}

inline void Add(int x) {
	f[pos[x]]++;
	if (++cnt[x] == 1) g[pos[x]]++;
}

inline void Del(int x) {
	f[pos[x]]--;
	if (--cnt[x] == 0) g[pos[x]]--;
}

inline void Ask(int x) {
	int l = nd[x].a, r = nd[x].b, id = nd[x].id;
	if (pos[r] - pos[l] < 2) {
		for (int i = l; i <= r; i++)
			if (cnt[i]) ans_1[id] += cnt[i], ans_2[id]++;
		return;
	}
	for (int i = l; i < L[pos[l] + 1]; i++)
		if (cnt[i]) ans_1[id] += cnt[i], ans_2[id]++;
	for (int i = L[pos[r]]; i <= r; i++)
		if (cnt[i]) ans_1[id] += cnt[i], ans_2[id]++;
	for (int i = pos[l] + 1; i < pos[r]; i++)
		ans_1[id] += f[i], ans_2[id] += g[i];
}

signed main() {
	n = R(), m = R();
	for (int i = 1; i <= n; i++) 
		a[i] = R();
	for (int i = 1; i <= m; i++)
		nd[i].l = R(), nd[i].r = R(), nd[i].a = R(), nd[i].b = R(), nd[i].id = i;
	block = sqrt(n);
	for (int i = 1; i <= n; i++) {
		pos[i] = (i - 1) / block + 1;
		if (pos[i] != pos[i - 1]) L[pos[i]] = i;
	}
	L[pos[n + 1] = pos[n] + 1] = n + 1;
	std::sort(nd + 1, nd + 1 + m);
	for (int i = 1, l = 1, r = 0; i <= m; i++) {
		while (l < nd[i].l) Del(a[l++]);
		while (l > nd[i].l) Add(a[--l]);
		while (r < nd[i].r) Add(a[++r]);
		while (r > nd[i].r) Del(a[r--]);
		Ask(i);
	}
	for (int i = 1; i <= m; i++)
		printf("%d %d
", ans_1[i], ans_2[i]);
	return 0;
}

Problem N: Permu

不会，咕着