D-query-初识莫队

概述

莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。

普通莫队

对于序列上的区间询问问题,如果从 [l, r][l,r] 的答案能够 O(1)O(1) 扩展到 [l – 1, r], [l + 1, r],[l, r + 1],[l, r – 1][l−1,r],[l+1,r],[l,r+1],[l,r−1] 的答案,那么可以在 O(n\sqrt n)O(n√n) 的复杂度内求出所有询问的答案。1
由于数学公式乱码,实现部分移步莫队算法学习笔记查看。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int num[1000010],vis[1000010],s[1000010];
int m,block,ans;
struct node
{
    int l,r,id;
    bool operator < (const node &c)const{
        if(l/block==c.l/block)
            return r<c.r;
        return l/block < c.l/block;
    }
}q[1000010];



void add(int x)
{
    vis[s[x]]++;
    if(vis[s[x]]==1)ans++;
}

void del(int x)
{
    vis[s[x]]--;
    if(vis[s[x]]==0)ans--;
}

int main()
{
    int n;
    scanf("%d",&n);
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(l<q[i].l)del(l),l++;
        while(l>q[i].l)l--,add(l);
        while(r<q[i].r)r++,add(r);
        while(r>q[i].r)del(r),r--;
        num[q[i].id]=ans;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",num[i]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注