很久之前写线段树的时候…就碰到过好多诸如 “查询区间颜色种类” “查询区间众数”…这种毒瘤的题, 那时候幼稚的宽嫂还不知道什么叫分块, 什么叫莫队, 带着根号的复杂度究竟有什么意义, 只是绞尽脑汁想如何用仅会的一点知识来解决这个问题…

话说这个中二的开头什么鬼啊

莫队算法

例行Orz莫涛

无修改

莫队, 就是一种elegent elephant 的暴力,
用来解决 只要你能写出$O(1)$扩大1单位边界的暴力 的区间查询(单点修改)问题

在序列上就是普通的暴力转移, 加入一个点, 修改答案, 加上这个点对答案的贡献, 但是我们要利用多个询问区间的大量重复, 用恰当的方式顺序进行转移, 来让复杂度稳定在一个可以接受的范围

这个顺序说起来其实真的简单, 就是分个块(其实这个块并没有什么用, 只是为了把询问分开而已), 按照 [左端点所在的块 -> 右端点] 这样的优先级来排序(别和我讲什么***距离, 最差复杂度不还是一样?), 然后暴力转移即可, 完了, 是不是很简单? 所以莫队的难点就在于你想不出暴力?

根据一些玄学(dalao: 这个怎么玄学了啊, 这不就是@#$%#$%@#$)的复杂度证明, 反正他是对的($O(n\sqrt n)$)QAQ

至于这个证明捏…我直接忽略好了…复杂到让人不想看的证明是赶走初学者最好的方式(没错我就是被赶走了好几个月 而且其实是我不会证明)

带修改

带修改说起来其实也简单, 把修改过几次作为一个时间戳, 也加入排序就好啦, 修改的时候暴力改就行(真 暴力本质)…

几道例题

沙茶的代码

写法上学习了这个dalao, 感觉写的非常干净漂亮elegant, 我永远爱LXL莫队.jpg

又及, 都没有根号平衡, 可能被卡

小Z的袜子

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAXN (50000 + 5)
#define LL long long
#define INF (0x7ffffff)
#define pii pair<LL, LL>
using namespace std;
struct qu
{
    int bh, le, ri;
} que[MAXN];
int n, q, a[MAXN], block, cnt[MAXN], allcnt;
pii ans, ask[MAXN];
void add(int);
void del(int);
void solve();
bool cmp(qu, qu);
LL gcd(LL, LL);
int main(int argc, char const *argv[])
{
    scanf("%d%d", &n, &q);
    block = sqrt(n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &que[i].le, &que[i].ri);
        que[i].bh = i;
        if (que[i].le == que[i].ri)
        {
            ask[i] = make_pair(0, 1);
            que[i].le = que[i].ri = INF;
        }
    }
    solve();
    for (int i = 1; i <= q; i++)
        printf("%lld/%lld\n", ask[i].first, ask[i].second);
    return 0;
}
LL gcd(LL a, LL b)
{
    return ((b == 0) ? (a) : gcd(b, a % b));
}
bool cmp(qu x, qu y)
{
    if (x.le / block == y.le / block)
        return x.ri < y.ri;
    else
        return x.le < y.le;
}
void add(int x)
{
    if (cnt[a[x]] > 0)
        ans.first -= (LL)cnt[a[x]] * (cnt[a[x]] - 1);
    ++cnt[a[x]], ++allcnt;
    if (cnt[a[x]] > 0)
        ans.first += (LL)cnt[a[x]] * (cnt[a[x]] - 1);
    ans.second = (LL)allcnt * (allcnt - 1);
}
void del(int x)
{
    if (cnt[a[x]] > 0)
        ans.first -= (LL)cnt[a[x]] * (cnt[a[x]] - 1);
    --cnt[a[x]], --allcnt;
    if (cnt[a[x]] > 0)
        ans.first += (LL)cnt[a[x]] * (cnt[a[x]] - 1);
    if (allcnt > 0)
        ans.second = (LL)allcnt * (allcnt - 1);
    else
        ans.second = 0;
}
void solve()
{
    sort(que + 1, que + q + 1, cmp);
    int le = que[1].le, ri = que[1].ri;
    for (int i = le; i <= ri; i++)
        add(i);
    ask[que[1].bh] = ans;
    for (int i = 2; i <= q; i++)
    {
        if (que[i].le == INF)    break;
        while (que[i].le > le)    del(le++);
        while (que[i].le < le)    add(--le);
        while (que[i].ri < ri)    del(ri--);
        while (que[i].ri > ri)    add(++ri);
        ask[que[i].bh] = ans;
    }
    for (int i = 1; i <= q; i++)
    {
        LL ta = gcd(ask[i].first, ask[i].second);
        ask[i].first /= ta, ask[i].second /= ta;
    }
}

/*
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
*/

数颜色

时间那个地方还是有些细节的…

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAXN (10000 + 5)
#define MAXQ (10000 + 5)
#define MAXZ (1000000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct qu
{
    int le, ri, time, bh;
    bool xg;
} que[MAXQ];
int n, q, l, r, cnt[MAXZ], ans, a[MAXN], blockn, ask[MAXQ];
void xg(int, int);
void add(int);
void del(int);
void solve();
bool cmp(qu, qu);
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("wa.out", "w", stdout);
#endif
    scanf("%d%d", &n, &q);
    blockn = sqrt(n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int cntt = 0, cntq = 0;
    for (int i = 1; i <= q; i++)
    {
        char sre;
        int srx, sry;
        do
            sre = getchar();
        while (sre > 'Z' || sre < 'A');
        scanf("%d%d", &srx, &sry);
        que[i].le = srx, que[i].ri = sry;
        que[i].xg = (sre == 'R');
        if (sre == 'R')    que[i].time = ++cntt;
        else    que[i].bh = ++cntq, que[i].time = (que[i - 1].xg ? ++cntt : cntt); // 这里的时间段要特别注意 
    }
    solve();
    for (int i = 1; i <= cntq; i++)
        printf("%d\n", ask[i]);
    return 0;
}
bool cmp(qu x, qu y)
{
    if (x.time != y.time)
        return x.time < y.time;
    if (x.le / blockn == y.le / blockn)
        return x.ri < y.ri;
    else
        return x.le < y.le;
}
void solve()
{
    sort(que + 1, que + q + 1, cmp);
    int beg = 1;
    while (que[beg].xg)
    {
        a[que[beg].le] = que[beg].ri;
        ++beg;
    }
    l = que[beg].le, r = que[beg].ri;
    for (int i = l; i <= r; i++)
        add(i);
    ask[que[beg].bh] = ans;
    for (int i = beg + 1; i <= q; i++)
    {
        if (que[i].xg)
        {
            xg(que[i].le, que[i].ri);
            continue;
        }
        while (l < que[i].le)
            del(l++);
        while (l > que[i].le)
            add(--l);
        while (r < que[i].ri)
            add(++r);
        while (r > que[i].ri)
            del(r--);
        ask[que[i].bh] = ans;
    }
}
void add(int x)
{
    if (!cnt[a[x]])
        ++ans;
    ++cnt[a[x]];
}
void del(int x)
{
    --cnt[a[x]];
    if (!cnt[a[x]])
        --ans;
}
void xg(int wz, int x)
{
    if (l > wz || r < wz)
    {
        a[wz] = x;
        return ;
    }
    if (wz - l > r - wz)
        while (l <= wz)    del(l++);
    else
        while (r >= wz)    del(r--);
    a[wz] = x;

}

/*
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
*/

By 沙茶 Cansult