首页 > 代码库 > _bzoj2038 [2009国家集训队]小Z的袜子(hose)【莫队】
_bzoj2038 [2009国家集训队]小Z的袜子(hose)【莫队】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2038
裸的莫队,注意要先移动右端点再移动左端点。
#include <cstdio> #include <algorithm> #include <cmath> const int maxn = 50005, maxm = 50005; int n, m, c[maxn], s[maxn], l, r, siz; long long fenzi[maxm], fenmu[maxm], tem, same; struct st { int l, r; int id; } q[maxm]; bool cmp(const st & aa, const st & ss) { if (aa.l / siz == ss.l / siz) { return aa.r < ss.r; } return aa.l / siz < ss.l / siz; } inline long long gcd(long long aa, long long ss) { long long tt; while (ss) { tt = aa; aa = ss; ss = tt % ss; } return aa; } int main(void) { //freopen("in.txt", "r", stdin); scanf("%d%d", &n, &m); siz = (int)sqrt((float)n + 0.5f); for (int i = 1; i <= n; ++i) { scanf("%d", c + i); } for (int i = 1; i <= m; ++i) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } std::sort(q + 1, q + m + 1, cmp); for (int i = q[1].l; i <= q[1].r; ++i) { ++s[c[i]]; } for (int i = 0; i <= n; ++i) { same += (long long)s[i] * (long long)(s[i] - 1) >> 1; } l = q[1].l; r = q[1].r; fenmu[q[1].id] = (long long)(q[1].r - q[1].l + 1) * (long long)(q[1].r - q[1].l) >> 1; fenzi[q[1].id] = same; tem = gcd(fenmu[q[1].id], fenzi[q[1].id]); fenmu[q[1].id] /= tem; fenzi[q[1].id] /= tem; for (int i = 2; i <= m; ++i) { fenmu[q[i].id] = (long long)(q[i].r - q[i].l + 1) * (long long)(q[i].r - q[i].l) >> 1; while (r < q[i].r) { ++r; same += s[c[r]]; ++s[c[r]]; } while (r > q[i].r) { same += 1 - s[c[r]]; --s[c[r]]; --r; } while (l > q[i].l) { --l; same += s[c[l]]; ++s[c[l]]; } while (l < q[i].l) { same += 1 - s[c[l]]; --s[c[l]]; ++l; } fenzi[q[i].id] = same; tem = gcd(fenmu[q[i].id], fenzi[q[i].id]); fenmu[q[i].id] /= tem; fenzi[q[i].id] /= tem; } for (int i = 1; i <= m; ++i) { printf("%lld/%lld\n", fenzi[i], fenmu[i]); } return 0; }
_bzoj2038 [2009国家集训队]小Z的袜子(hose)【莫队】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。