$分块$

$$基础莫队$$

$莫队简介$

莫队是基于分块思想的离线数据结构

用于解决不能用分块直接解决的问题

$基本操作$

给定一个序列

支持询问[l,r]中的可加减操作

$引入$

首先可以想到离线暴力算法,用两个指针维护,时间复杂度为指针移动次数,即$O(n^2)$

莫队采用优化询问顺序的思想,优化了指针移动的次数

$分析$

若序列长度为$n$,分块后每段长度为$a$,共有$\frac{n}{a}$块,m次询问(根据数据范围,取合适的$len$)

基础莫队的排序标准为:

1. 比较左端点所在的块,从左到右排序
2. 若所在块相等,则比较右端点,从从左到右排序

左指针的移动距离为: $am+n$
右指针的移动距离为: $\frac{n^2}{a}$

当$a$取到$\sqrt{\frac{n^2}{m}}$时最优

时间复杂度为$O(n\sqrt{m})$

$Code$

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

const int N = 50010, M = 200010, S = 1000010;
struct Node {
    int id, l, r;
}q[M];
int n, m, len=1;
int a[N], ans[M];
int cnt[S];

int get(int i)
{
    return i / len;
}

bool cmp(Node a, Node b)
{
    int al = get(a.l), bl = get(b.l);
    if (al != bl)return al < bl;
    return a.r > b.r;
}

void add(int w, int& res)
{
    if (++ cnt[w] == 1)res ++ ;
}

void sub(int w, int& res)
{
    if (-- cnt[w] == 0)res -- ;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )scanf("%d", &a[i]);
    scanf("%d", &m);
    len = max(1, (int)sqrt((double)n * n / m));
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q, q + m, cmp);
    for (int k = 0, i = 1, j = 0, res = 0; k < m; k ++ )
    {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (j < r)add(a[ ++ j], res);
        while (j > r)sub(a[j -- ], res);
        while (i < l)sub(a[i ++ ], res);
        while (i > l)add(a[ -- i], res);
        ans[id] = res;
    }
    for (int i = 0; i < m; i ++ )printf("%d\n", ans[i]);
    return 0;
}