首页 > 代码库 > HDU 5145 NPY and girls 莫队算法
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\n", ans[i]); } } return 0;}
HDU 5145 NPY and girls 莫队算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。