莫队

参考资料：

洛谷

OIwiki

Q: 莫队算法解决什么问题？

A: 离线区间询问问题

普通莫队算法

核心：

• 已知某区间的询问结果，能够通过$O(1)$的复杂度得到相邻区间的询问结果
• 对所有的询问进行排序，来降低查找所需步数
• 排序中采用分块排序的方式

模板题：洛谷 P2709 小B的询问

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define mmax 500010

typedef struct{
    int order;
    int block;
    int ans;
    int l;
    int r;
}p;

bool cmp_l(p a, p b)
{
    return a.l < b.l;
}

bool cmp_block(p a, p b)
{
    if (a.block == b.block) return a.r < b.r;
    else return a.block < b.block;
}
// 奇偶分块的cmp，只需将line66的cmp函数替换成这个就可以了
bool cmp_block_odd_even(p a, p b)
{
    if (a.block == b.block) {
        if (a.block % 2)return a.r < b.r;
        else return a.r > b.r;
    }
    else return a.block < b.block;
}

bool cmp_order(p a, p b)
{
    return a.order < b.order;
}


int main()
{
    int a[mmax];
    int cnt[mmax];
    p inq[mmax];
    for (int i = 0; i < mmax; i++)
        cnt[i] = 0;
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        inq[i].l = a;
        inq[i].r = b;
        inq[i].order = i;
    }
    int block_lenth = n / int(sqrt(m * 2 / 3));
    for (int i = 0; i < m; i++)
    {
        inq[i].block = inq[i].l / block_lenth;
    }
    sort(inq, inq + m, cmp_block);
    int ans = 0;
    for (int i = inq[0].l - 1; i < inq[0].r; i++)
    {
        cnt[a[i]]++;
        ans += 2 * cnt[a[i]] - 1;
    }
    inq[0].ans = ans;
    int lp = inq[0].l;
    int rp = inq[0].r;


    for (int i = 1; i < m; i++)
    {
        while(lp < inq[i].l) 
        { 
            ans -= 2 * cnt[a[lp - 1]] - 1; 
            cnt[a[lp - 1]]--; 
            lp++; 
        }
        while(lp > inq[i].l) 
        { 
            lp--;
            ans += 2 * cnt[a[lp - 1]] + 1; 
            cnt[a[lp - 1]]++;          
        }
        while(rp > inq[i].r) 
        { 
            ans -= 2 * cnt[a[rp - 1]] - 1; 
            cnt[a[rp - 1]]--; 
            rp--; 
        }
        while(rp < inq[i].r) 
        { 
            rp++; 
            ans += 2 * cnt[a[rp - 1]] + 1; 
            cnt[a[rp - 1]]++; 
        }
        inq[i].ans = ans;
    }

    sort(inq, inq + m, cmp_order);
    for (int i = 0; i < m; i++)
        cout << inq[i].ans << endl;

}

细节：

最后的区间上限下限左右移动，注意是先定位再移动或是先移动再定位；区间元素增加的一般先移动再定位，元素减少的先定位再移动。（其实没什么用，只不过做题的时候脑子有点糊，随手写一下）

经过实测

• int block_lenth = n / int(sqrt(m * 2 / 3))为较佳分块长度；
• 奇偶分块在大多数情况下能有一些提升，虽说理论上能提升一倍效率，但是实测并不能到达该效果（但是有总比没有好）。