P1972 [SDOI2009]HH的项链

莫队 信息 洛谷

---

看到题解里提到一种神奇的算法——莫队，据说可以解决一切区间问题。。。
核心思想就是利用当前求的区间的值推知接下来要求的区间的值，因为已知区间f[l][r]，我们可以很快地求得区间$f[l\pm1][r]$或者$f[l][r\pm1]$，因而可以逐步地推出下一个区间要求的值。
但是如果单纯只是这样算的话，复杂度有$O(n^2)$，这也没有体现莫队”优雅的暴力“的美称。
于是就有了莫队算法的精华——分块，我们知道，在推出下一个区间的过程中，尽量地使下一个区间和当前的区间的交集最大，就可以让推的过程尽量地短，于是按照一定地顺序求解，也就是我们通常讲的离线算法，在此就显得尤为重要了。
单纯的排序，即以左端点为第一关键字，右端点为第二关键字，固然可以减少左指针的移动，但右边的指针则会跑来跑去。为了尽量让右指针来回的次数少，可以相对地牺牲一点左边。把所有的区间按左端点分块，相同一块的区间再按右端点排序，这样一来，单纯就一个块而言，左指针只会在自己那一块里移动，右指针只会从头到尾扫一遍，这样就节省了很多时间。
分块大多分为$\sqrt n$块，每块$\sqrt n$个区间，至于为什么这样分，我也不知道。。。
算一算时间复杂度，就是

$$运算次数=块数量*（块内区间数*左指针的移动范围大小+区间总数）$$
即 $$运算次数=\sqrt n*(\sqrt n*\sqrt n+n)$$
就得到一个$O(n\sqrt n)$的算法了
这道题就是个裸的莫队吧
下面是代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int judge[10000001];
int seq[50001],p[200001];
struct node
{
    int l,r,t,id,ans;
}a[200001];
bool my_comp(const node x,const node y)
{
    if(x.t==y.t)return x.r<y.r;
    return x.l<y.l;
}
int main()
{
    int n,m;
    cin>>n;
    int len=sqrt(n);
    for(int i=1;i<=n;i++)
        scanf("%d",&seq[i]);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].t=a[i].l/len;
        a[i].id=i;
    }
    sort(a+1,a+1+m,my_comp);
    int left=0,right=0,ans=0;
    for(int i=1;i<=m;i++)
    {
        while(left<a[i].l)
        {
            judge[seq[left]]--;
            if(judge[seq[left++]]==0)
                ans--;
        }
        while(left>a[i].l)
        {
            if(!judge[seq[left-1]])
                ans++;
            judge[seq[--left]]++;
        }
        while(right<a[i].r)
        {
            if(!judge[seq[right+1]])
                ans++;
            judge[seq[++right]]++;
        }
        while(right>a[i].r)
        {
            judge[seq[right]]--;
            if(!judge[seq[right--]])
                ans--;
        }
        p[a[i].id]=ans;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",p[i]);
    return 0;
}

参考： modui