莫队

· · 个人记录

莫队（离线算法）

离线算法：收集所有问题，同意计算答案。

应用场景：多次区间询问、区间扩张、区间收缩。

莫队：对询问排序（先对序列分块 \sqrt n）

莫队是一个很好写的高端暴力方式，但有时确实无法被替代。

【板】P3901 数列找不同

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
int n, q, val[MAX], ans[MAX], t[MAX], res, len; // res 为当前区间信息，ans[] 为每一个问题的答案
struct Qry{int l, r, id;} qry[MAX]; // 询问
bool cmp(Qry a,Qry b)
{
    int ida = (a.l - 1) / len + 1; // 计算第一个区间的左边界块号
    int idb = (b.l - 1) / len + 1; // 计算第二个区间的左边界块号
    return ida < idb || (ida == idb && a.r < b.r);
}
void add(int pos)
{
    t[val[pos]] += 1;
    if(t[val[pos]] > 1) res += 1;
}// 加入对应元素并且重算区间信息。

void del(int pos)
{
    t[val[pos]] -= 1;
    if(t[val[pos]] >= 1) res -= 1;
}// 去除对应元素并且重算区间信息。

void mo()
{
    len = sqrt(n); // 计算块长
    sort(qry + 1, qry + q + 1, cmp);

    for(int i = 1, l = 1, r = 0; i <= q; ++i)
    {
        // 先扩后缩，保证中间区间合法
        while(l > qry[i].l) add(--l);
        while(r < qry[i].r) add(++r);
        while(r > qry[i].r) del(r--);
        while(l < qry[i].l) del(l++);

        ans[qry[i].id] = res;
    }
}

int main()
{
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=1; i<=q; i++) cin >> qry[i].l >> qry[i].r, qry[i].id = i;

    mo();
    for(int i=1; i<=q; i++)
    {
        if(ans[i]) cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
}

带修莫队

【板】P1494 [国家集训队] 小 Z 的袜子

#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAX = 1e5+5;
int n, q, val[MAX], ans1[MAX], ans2[MAX], num[MAX], sum, len; // res 为当前区间信息，ans[] 为每一个问题的答案
struct Qry{int l, r, id;} qry[MAX]; // 询问
bool cmp(Qry a,Qry b)
{
    int ida = (a.l - 1) / len + 1; // 计算第一个区间的左边界块号
    int idb = (b.l - 1) / len + 1; // 计算第二个区间的左边界块号
    return ida < idb || (ida == idb && a.r < b.r);
}
void add(int pos)
{
    sum += num[val[pos]];
    ++num[val[pos]];
}// 加入对应元素并且重算区间信息。

void del(int pos)
{
    --num[val[pos]];
    sum -= num[val[pos]];
}// 去除对应元素并且重算区间信息。

void mo()
{
    len = sqrt(n); // 计算块长
    sort(qry + 1, qry + q + 1, cmp);

    for(int i = 1, l = 1, r = 0; i <= q; ++i)
    {
        // 先扩后缩，保证中间区间合法
        while(l > qry[i].l) add(--l);
        while(r < qry[i].r) add(++r);
        while(r > qry[i].r) del(r--);
        while(l < qry[i].l) del(l++);

        ans1[qry[i].id] = sum;
        ans2[qry[i].id] = (r - l + 1) * (r - l) / 2;
        if(ans1[qry[i].id] == 0) ans2[qry[i].id] = 1;
        else
        {
            int g = __gcd(ans1[qry[i].id], ans2[qry[i].id]);
            ans1[qry[i].id] /= g;
            ans2[qry[i].id] /= g;
        }
    }
}

signed main()
{
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=1; i<=q; i++) cin >> qry[i].l >> qry[i].r, qry[i].id = i;

    mo();
    for(int i=1; i<=q; i++) cout << ans1[i] << '/' << ans2[i] << endl;
    return 0;
}

回滚莫队

【板】P5906 【模板】回滚莫队&不删除莫队

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;

int n, q, l, r, val[N], ans[N], res, len, maxx[N], minn[N], block[N]; // res 为当前区间信息，ans[] 为每一个问题的答案
struct Qry {int l, r, id;} qry[N]; // q 个询问
bool cmp(Qry a,Qry b) {return block[a.l] < block[b.l] || (block[a.l] == block[b.l] && a.r < b.r);}
struct His {int x, max_w, min_w, pre_res;}; stack<His> his; // History

void Discretize(int *a,int n) 
{
    vector<int> tmp;
    for(int i=1; i<=n; ++i) tmp.push_back(a[i]);

    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    for(int i=1; i<=n; ++i) a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin() + 1;
} // 离散化

void add(int pos, bool save) 
{
    int w = val[pos];
    if(save == true) his.push({w, maxx[w], minn[w], res});
    // 记录原本的值
    maxx[w] = max(maxx[w], pos);
    minn[w] = min(minn[w], pos);
    res = max(res, maxx[w] - minn[w]);
} // 加入对应元素并且重算区间信息，save表示是否记录信息

void clear()
{
    for(int i=1; i<=n; ++i) maxx[i] = 0, minn[i] = n + 1;
    res = 0;
} // 清空记录信息，可支持 O(n) 清空

void roll_back()
{
    while(his.empty() == false) 
    {
        auto [x, max_w, min_w, pre_res] = his.top();
        his.pop();
        maxx[x] = max_w;
        minn[x] = min_w;
        res = pre_res;
    }
} // 全部回滚

void rollback_mo() 
{
    Discretize(val, n);

    len = sqrt(n);
    // 预处理 全下标块号
    for(int i=1; i<=n; ++i) block[i] = (i - 1) / len + 1;
    sort(qry + 1, qry + q + 1, cmp);

    for(int i = 1, l, r; i <= q; ++i) 
    {
        // 到达新块：1.重置起点；2.重置信息。
        if(block[qry[i].l] != block[qry[i - 1].l]) r = min(n, block[qry[i].l] * len), l = r + 1, clear();

        // 正常 点
        if(block[qry[i].l] != block[qry[i].r]) 
        {
            while(r < qry[i].r) add(++r, false); // 右边界对齐，不记录
            int ori_l = l;
            while(l > qry[i].l) add(--l, true); // 左边界对齐，记录
            l = ori_l; // 左边界还原
        }
        // 对角线旁的点暴力，记录
        // 因为对角线旁的点处理在正常点之前，此时区间信息为空，所以可以拿来复用一下
        else for(int j = qry[i].l; j <= qry[i].r; ++j) add(j, true);
        ans[qry[i].id] = res;

        roll_back(); // 回滚操作
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n; for(int i = 1;i <= n;++i) cin >> val[i];
    cin >> q; for(int i = 1;i <= q;++i) cin >> l >> r, qry[i] = {l, r, i};
    rollback_mo();
    for(int i = 1;i <= q;++i) cout << ans[i] << endl;

    return 0;
}