ToB企服应用市场:ToB评测及商务社交产业平台

标题: 根号分治莫队 [打印本页]
作者: 勿忘初心做自己    时间: 2024-8-14 15:13
标题: 根号分治莫队
莫队

参考文章：
莫队细讲——从零开始学莫队
莫队算法——从入门到黑题
oiwiki--普通莫队
莫队简介

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经Codeforces 的高手圈里小范围传播，但是莫涛是第一个对莫队算法进行具体归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。
莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操纵。
普通莫队算法

情势

假设 \(n = m\)，那么对于序列上的区间询问问题，如果从 \([l, r]\) 的答案能够 \(O(1)\) 扩展到 \([l-1, r]\), \([l+1, r]\), \([l, r+1]\), \([l, r-1]\)（即与 \([l, r]\) 相邻的区间）的答案，那么可以在 \(O(n\sqrt{n})\) 的复杂度内求出所有询问的答案。
解释

离线后排序，次序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案（一步一步移动即可）。
排序方法

对于区间 \([l, r]\), 以 \(l\) 所在块的编号为第一关键字，\(r\) 为第二关键字从小到大排序。
略.......
直接上题目
P1494 [国家集训队] 小 Z 的袜子
[国家集训队] 小 Z 的袜子

题目形貌

upd on 2020.6.10 ：更新了时限。
作为一个生活散漫的人，小 Z 天天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听其自然……
具体来说，小 Z 把这 \(N\) 只袜子从 \(1\) 到 \(N\) 编号，然后从编号 \(L\) 到 \(R\) 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完备的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z，他有多大的概率抽到两只颜色雷同的袜子。当然，小 Z 希望这个概率尽量高，以是他可能会询问多个 \((L,R)\) 以方便自己选择。
然而数据中有 \(L=R\) 的情况，请特判这种情况，输出0/1。
输入格式

输入文件第一行包含两个正整数 \(N\) 和 \(M\)。\(N\) 为袜子的数目，\(M\) 为小 Z 所提的询问的数目。接下来一行包含 \(N\) 个正整数 \(C_i\)，其中 \(C_i\) 表示第 \(i\) 只袜子的颜色，雷同的颜色用雷同的数字表示。再接下来 \(M\) 行，每行两个正整数 \(L, R\) 表示一个询问。
输特别式

包含 \(M\) 行，对于每个询问在一行中输出分数 \(A/B\) 表示从该询问的区间 \([L,R]\) 中随机抽出两只袜子颜色雷同的概率。若该概率为 \(0\) 则输出 0/1，否则输出的 \(A/B\) 必须为最简分数。（详见样例）
样例 #1

样例输入 #1
  1. 6 4
  2. 1 2 3 3 3 2
  3. 2 6
  4. 1 3
  5. 3 5
  6. 1 6
复制代码
样例输出 #1
  1. 2/5
  2. 0/1
  3. 1/1
  4. 4/15
复制代码
提示

\(30\%\) 的数据中，\(N,M\leq 5000\)；
\(60\%\) 的数据中，\(N,M \leq 25000\)；
\(100\%\) 的数据中，\(N,M \leq 50000\)，\(1 \leq L \leq R \leq N\)，\(C_i \leq N\)。
AC代码：

[code]#include#define int long long#define debug() cout n >> q; // 读取数组大小和查询数目    for (int i = 1; i > c; // 读取数组元素    for (int i = 0; i < q; i++) {        int l, r;        cin >> l >> r; // 读取每个查询的区间 [l, r]        que = {l, r, i}; // 存储查询        ans2 = (r - l) * (r - l + 1) / 2; // 计算分母    }    // 按照莫队算法的分块策略对查询进行排序    sort(que, que + q, [&](array a, array b) {        int d = a[0] / B;        if (a[0] / B != b[0] / B) return a[0] / B < b[0] / B;        //if (d % 2 == 1) return a[1] < b[1];        //else return a[1] > b[1];        return a[1] que[0]) l--, add(l); // 扩展左边界        while (r > que[1]) del(r), r--; // 收缩右边界        while (l < que[0]) del(l), l++; // 收缩左边界        ans[que[2]] = tmp; // 记录当前查询的结果    }    // 输出每个查询的结果    for (int i = 0; i < q; i++) {        if (ans2 == 0 && ans == 0) { // 如果分子和分母都为 0            cout id>>x>>y;        if(id==1)        {            for(int i=1;i



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4