莫队算法

· · 算法·理论

莫队算法

莫队算法的核心思想是将所有查询重新排序，使得相邻查询的区间移动代价最小化，从而均摊查询复杂度。

板子题：CF86D

用于离线的统计一个区间内不同数字出现的次数，非常高效

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define MAXN 1000001
#define LL long long
using namespace std;

inline LL read()
{
    LL x = 0; char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') x = x*10 + c-'0', c = getchar();
    return x;
}

void write(LL x)
{
    if(x < 0) { putchar('-'); x=-x; }
    if(x > 9) { write(x/10); putchar(x % 10 + '0'); }
    else putchar(x + '0');
    return;
}

struct Query
{
    LL l, r, id;
} qs[MAXN];

LL s[MAXN], blockSize, ans[MAXN], freq[MAXN];

bool cmp(Query a, Query b)
{
    if(a.l / blockSize != b.l / blockSize) return a.l < b.l;
    return (a.l / blockSize % 2) ? (a.r < b.r) : (a.r > b.r);
}

int main()
{
    LL n, t;
    n = read(); t = read();
    for(LL x = 1; x <= n; x++) s[x] = read();

    for(LL x = 1; x <= t; x++)
    {
        qs[x].l = read(); qs[x].r = read();
        qs[x].id = x;
    }

    blockSize = max(1LL, (LL)(n / sqrt(t)));
    sort(qs+1, qs+t+1, cmp);

    LL cl = 1, cr = 0, sum = 0;

    for(LL x = 1; x <= t; x++)
    {
        Query q = qs[x];
        while(cl > q.l)
        {
            LL tmp = s[--cl];
            sum -= freq[tmp] * freq[tmp] * tmp;
            sum += ++freq[tmp] * freq[tmp] * tmp;
        }
        while(cr < q.r)
        {
            LL tmp = s[++cr];
            sum -= freq[tmp] * freq[tmp] * tmp;
            sum += ++freq[tmp] * freq[tmp] * tmp;
        }
        while(cl < q.l)
        {
            LL tmp = s[cl++];
            sum -= freq[tmp] * freq[tmp] * tmp;
            sum += --freq[tmp] * freq[tmp] * tmp;
        }
        while(cr > q.r)
        {
            LL tmp = s[cr--];
            sum -= freq[tmp] * freq[tmp] * tmp;
            sum += --freq[tmp] * freq[tmp] * tmp;
        }
        ans[q.id] = sum;
    }

    for(LL x = 1; x <= t; x++)
    {
        write(ans[x]);
        putchar('\n');
    }
    return 0;
}

卡常，不需要离散化，但每次统计freq的时候都要更新一下ans，这样可以更高效