HDU 5145 NPY and girls 莫队算法

对于这类区间查询的问题，如果可以用O(1)的复杂度推到一个曼哈顿距离为1的另外区间的话，就可以直接用莫队算法搞。

从网上搜到的有两种搞法。第一种是先建立曼哈顿距离最小生成树，然后直接dfs遍历整棵树来求解的。

还有一种是先分块，然后把查询按照块的编号为第一关键字，右边界为第二关键字排序，排序直接直接暴力转移。

这样做的复杂度是n * sqrt(n)，后面那个sqrt(n)取决于是怎么分块的。

仔细想想感觉这样子搞复杂度差不多就是这样，因为在同一个块中的复杂度怎么搞都是sqrt(n)级别的，就算是跨越的块的区间因为r是排过序的，复杂度也不会太高。

分块写比较简单，先拍了。。至于先建树那种搞法下次有机会再敲吧。

#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

//乘法逆元
LL ex_gcd(LL a, LL b, LL &x, LL &y)
{
	if (a == 0 && b == 0) return -1;
	if (b == 0) { x = 1; y = 0; return a; }
	LL d = ex_gcd(b, a%b, y, x);
	y -= a / b*x;
	return d;
}
LL Get_inv(LL a, LL n = MOD)
{
	LL x, y, d = ex_gcd(a, n, x, y);
	if (d == 1) return (x%n + n) % n;
	else return -1;
}

const int maxn = 3e4 + 10;

LL nowcnt[maxn], a[maxn], n, m;
LL ans[maxn], unit_size, inv[maxn];

struct Q {
	int l, r, id;
	bool operator < (const Q &x) const {
		if (l / unit_size == x.l / unit_size) return r < x.r;
		return l / unit_size < x.l / unit_size;
	}
};

Q q[maxn];

void gao() {
	LL nowl = q[1].l, nowr = q[1].r;
	LL nowval = 1, nowc = 0;
	for (int i = nowl; i <= nowr; i++) {
		nowc++; nowcnt[a[i]]++;
		nowval = (nowval * nowc) % MOD;
		nowval = (nowval * inv[nowcnt[a[i]]]) % MOD;
	}
	ans[q[1].id] = nowval;
	for (int i = 2; i <= m; i++) {
		while (nowl > q[i].l) {
			nowl--; nowc++;
			nowcnt[a[nowl]]++;
			nowval = (nowval * nowc) % MOD;
			nowval = (nowval * inv[nowcnt[a[nowl]]]) % MOD;
		}
		while (nowr < q[i].r) {
			nowr++; nowc++;
			nowcnt[a[nowr]]++;
			nowval = (nowval * nowc) % MOD;
			nowval = (nowval * inv[nowcnt[a[nowr]]]) % MOD;
		}
		while (nowr > q[i].r) {
			nowval = (nowval * inv[nowc]) % MOD;
			nowval = (nowval * nowcnt[a[nowr]]) % MOD;
			nowcnt[a[nowr]]--;
			nowr--; nowc--;
		}
		while (nowl < q[i].l) {
			nowval = (nowval * inv[nowc]) % MOD;
			nowval = (nowval * nowcnt[a[nowl]]) % MOD;
			nowcnt[a[nowl]]--;
			nowl++; nowc--;
		}
		ans[q[i].id] = nowval;
	}
}


int main() {
	for (int i = 1; i <= 30000; i++) inv[i] = Get_inv(i) % MOD;
	int T; scanf("%d", &T);
	while (T--) {
		memset(nowcnt, 0, sizeof(nowcnt));
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= m; i++) {
			scanf("%d%d", &q[i].l, &q[i].r);
			q[i].id = i;
		}
		unit_size = (int)sqrt((double)(n));
		if (unit_size <= 0) unit_size = 1;
		sort(q + 1, q + 1 + m);
		gao();
		for (int i = 1; i <= m; i++) {
			printf("%I64d
", ans[i]);
		}
	}
	return 0;
}