根号分治莫队

莫队

参考文章:
莫队细讲——从零开始学莫队
莫队算法——从入门到黑题
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

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

样例输出 #1

2/5
0/1
1/1
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代码:

#include<bits/stdc++.h>
#define int long long
#define debug() cout<<"----------debug-------------"
using namespace std;

const int N = 500010; // 定义数组最大大小
int n, q; // n 是数组大小,q 是查询数量
int c[N]; // 存储输入数组
array<int, 3> que[N]; // 存储查询的数组,每个查询是一个三元组 {l, r, i}
int B = 750; // 分块的大小
int ans[N]; // 存储每个查询的结果
int tmp = 0; // 临时变量,用于计算当前区间内不同元素对的个数
int ans2[N]; // 记录每个查询的分母
int cnt[N]; // 记录每个数出现的次数

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出

    cin >> n >> q; // 读取数组大小和查询数量
    for (int i = 1; i <= n; i++)
        cin >> c[i]; // 读取数组元素

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r; // 读取每个查询的区间 [l, r]
        que[i] = {l, r, i}; // 存储查询
        ans2[i] = (r - l) * (r - l + 1) / 2; // 计算分母
    }

    // 按照莫队算法的分块策略对查询进行排序
    sort(que, que + q, [&](array<int, 3> a, array<int, 3> 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]<b[1];
    });

    int l = 1, r = 0; // 初始化指针 l 和 r

    // 添加元素时更新 tmp 和 cnt
    auto add = [&](int x) {
        tmp += cnt[c[x]];
        cnt[c[x]]++;
    };

    // 删除元素时更新 tmp 和 cnt
    auto del = [&](int x) {
        cnt[c[x]]--;
        tmp -= cnt[c[x]];
    };

    // 遍历每个查询,通过移动指针 l 和 r 来处理区间
    for (int i = 0; i < q; i++) {
        if (que[i][1] == que[i][0]) { // 如果查询区间长度为 0
            ans[que[i][2]] = 0;
            continue;
        }
        while (r < que[i][1]) r++, add(r); // 扩展右边界
        while (l > que[i][0]) l--, add(l); // 扩展左边界
        while (r > que[i][1]) del(r), r--; // 收缩右边界
        while (l < que[i][0]) del(l), l++; // 收缩左边界
        ans[que[i][2]] = tmp; // 记录当前查询的结果
    }

    // 输出每个查询的结果
    for (int i = 0; i < q; i++) {
        if (ans2[i] == 0 && ans[i] == 0) { // 如果分子和分母都为 0
            cout << "0/1" << endl;
            continue;
        }
        int d = __gcd(ans[i], ans2[i]); // 计算最大公约数
        cout << ans[i] / d << "/" << ans2[i] / d << endl; // 输出结果
    }

    return 0;
}

优化:

过程

我们看一下下面这组数据

// 设块的大小为 2 (假设)
1 1
2 100
3 1
4 100

手动模拟一下可以发现,r 指针的移动次数大概为 300 次,我们处理完第一个块之后,\(l = 2, r = 100\),此时只需要移动两次 l 指针就可以得到第四个询问的答案,但是我们却将 r 指针移动到 1 来获取第三个询问的答案,再移动到 100 获取第四个询问的答案,这样多了九十几次的指针移动。我们怎么优化这个地方呢?这里我们就要用到奇偶化排序。

什么是奇偶化排序?奇偶化排序即对于属于奇数块的询问,r 按从小到大排序,对于属于偶数块的排序,\(r\)从大到小排序,这样我们的\(r\) 指针在处理完这个奇数块的问题后,将在返回的途中处理偶数块的问题,再向 \(n\) 移动处理下一个奇数块的问题,优化了 \(r\) 指针的移动次数,一般情况下,这种优化能让程序快\(30\)% 左右。

  // 按照莫队算法的分块策略对查询进行排序
    sort(que, que + q, [&](array<int, 3> a, array<int, 3> 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];
    });

根号分治

根号分治,是暴力美学的集大成体现。与其说是一种算法,我们不如称它为一个常用的trick。

题目引入

首先,我们引入一道入门题目 CF1207F Remainder Problem

给你一个长度为 \(5×10^5\) 的序列,初值为 \(0\),你要完成 \(q\) 次操作,操作有如下两种:

  1. 1 x y: 将下标为 \(x\) 的位置的值加上 \(y\)
  2. 2 x y: 询问所有下标模 \(x\) 的结果为 \(y\) 的位置的值之和。

暴力解法

暴力1

首先有一种暴力就是按照题目所说的去做,开一个 \(5×10^5\) 大小的数组 \(a\) 去存,\(1\) 操作就对 \(a[x]\) 加上 \(y\)\(2\) 操作就枚举所有下标模 \(x\) 的结果为 \(y\) 的位置,统计他们的和。

对于这种暴力,\(1\) 操作的时间复杂度为 \(O(1)\)\(2\) 操作的时间复杂度为 \(O(n)\),所以在最坏情况下总时间复杂度可达 \(O(nq)\)

暴力2

经过思考,我们可以发现另外一种暴力:新开一个大小为 \(n×n\) 的二维数组 \(b\)\(b[i][j]\) 当前所有下标模 \(i\) 的结果为 \(j\) 的数的和是什么。对于每个 \(1\) 操作,动态的去维护这个 \(b\) 数组,在每次询问的时候直接输出答案即可。

对于这种暴力,\(1\) 操作的时间复杂度是枚举模数的 \(O(n)\)\(2\) 操作的时间复杂度为 \(O(1)\),总的时间复杂度为 \(O(nq)\)

根号分治策略

现在我们发现,这两种暴力对应了两种极端:一个是 \(1\) 操作的时间复杂度为 \(O(1)\),2 操作的时间复杂度为 \(O(n)\);另一个是 \(1\) 操作的时间复杂度是枚举模数的 \(O(n)\),2 操作的时间复杂度为 \(O(1)\)。那么,有没有办法让这两种暴力融合一下,均摊时间复杂度,达到一个平衡呢?

其实是有的。我们设定一个阈值 \(b\)

对于所有 \(≤b\) 的数,我们动态的维护暴力 \(2\)\(b\) 数组。每次 \(1\) 操作只需要枚举 \(b\) 个模数即可,故单次操作 \(1\) 的时间复杂度降为 \(O(b)\)

对于所有 \(>b\) 的数,我们就不在操作 \(1\) 中维护 \(b\),直接再询问答案时暴力枚举下标即可。显然,这 \(n\) 个下标中最多有 \(⌈n/b⌉\) 个下标对 \(x\) 取模余 \(y\) 找到第一个 \(y\) 后每次跳 \(x\),即可做到单次操作 \(2\) 时间复杂度为 \(O(n\sqrt{b})\)

所以,总时间复杂度就成为了 \(O(q×(b+n\sqrt{b}))\)。由基本不等式可得,\(b+n/b≥2√(b×n/b)=2√n\),当 \(b=\sqrt{n}\) 时取等。所以我们只需要让 \(b=\sqrt{n}\),就可以做到时间和空间复杂度均为\(O(q\sqrt{n})\) 的优秀算法了,可以通过此题。

代码:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N=5e5+30,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;
int q;
const int B=750;
int ans[B+10][B+10];
int a[N];
void solve()
{
    cin>>q;
    while(q--)
    {
        int id,x,y;
        cin>>id>>x>>y;
        if(id==1)
        {
            for(int i=1;i<=B;i++) ans[i][x%i]+=y;
            a[x]+=y;
        }
        else
        {
            if(x<=B) cout<<ans[x][y]<<endl;
            else
            {
                int temp=0;
                for(int i=y;i<=500000;i+=x)
                {
                    temp+=a[i];
                }
                cout<<temp<<endl;
            }
        }
    }

   
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _;
    _=1;
    //cin>>T;
    while(_--)
     {
         solve();
     }
     return 0;
} 

热门相关:九重神格   终归田居   林氏荣华   寻情仙使   大唐杨国舅