Pre

请确保您已经会普通莫队算法了。
如果您还不会,请食用这篇博客:【算法】 普通莫队算法

特点

  • 用于离线处理区间问题
  • 仅含单点修改
  • 能$O(1)$转移区间(和普通莫队一样)
  • 分块的每一块的大小是$n^\frac{2}{3}$
  • 复杂度$O(n^\frac{5}{3})$

带修改的莫队的询问排序方法为:

  • 第一关键字:左端点所在块编号,从小到大排序。
  • 第二关键字:右端点所在块编号,从小到大排序。
  • 第三关键字:经历的修改次数。也可以说是询问的先后,先询问的排前面。

对于前后两个区间的转移:

设当前询问为$a$,下一个询问为$b$,我们已知$a$,要求$b$。

首先我们像普通莫队一样转移左右端点。

这时候我们可能会发现$a$和$b$的经历的修改次数不同

怎么办呢?

然而,莫队就是个优雅的暴力。

假如$a$较$b$少修改了$p$次,那我们就把这$p$次修改一个一个从前往后暴力地加上去。假如$a$较$b$多修改了$q$次,那我们就把这$q$次修改从后往前还原掉。

具体怎么做呢?我们来看一道例题。

例题

数颜色 BZOJ – 2120

题目大意:给你一个序列,M个操作,有两种操作:

  1. 修改序列上某一位的数字
  2. 询问区间$[l,r]$中数字的种类数(多个相同的数字只算一个)

我们不难发现,如果不带操作1(修改)的话,我们就能轻松用普通莫队解决。

但是题目还带单点修改,所以用带修改的莫队

先考虑普通莫队的做法:

  • 每次扩大区间时,每加入一个数字,则统计它已经出现的次数,如果加入前这种数字出现次数为0,则说明这是一种新的数字,答案+1。然后这种数字的出现次数+1。
  • 每次减小区间时,每删除一个数字,则统计它删除后的出现次数,如果删除后这种数字出现次数为0,则说明这种数字已经从当前的区间内删光了,也就是当前区间减少了一种颜色,答案-1。然后这种数字的出现次数-1。

现在再来考虑修改:

  • 单点修改,把某一位的数字修改掉。假如我们是从一个经历修改次数为$i$的询问转移到一个经历修改次数为$j$的询问上,且$i<j$的话,我们就需要把第$i+1$个到第$j$个修改强行加上。
  • 假如$j<i$的话,则需要把第$i$个到第$j+1$个修改强行还原。

怎么强行加上一个修改呢?假设一个修改是修改第$pos$个位置上的颜色,原本$pos$上的颜色为$a$,修改后颜色为$b$,还假设当前莫队的区间扩展到了$[l,r]$。

  • 加上这个修改:我们首先判断$pos$是否在区间$[l,r]$内。如果是的话,我们等于是从区间中删掉颜色$a$,加上颜色$b$,并且当前颜色序列的第$pos$项的颜色改成$b$。如果不在区间$[l,r]$内的话,我们就直接修改当前颜色序列的第$pos$项为$b$。
  • 还原这个修改:等于加上一个修改第$pos$项、把颜色$b$改成颜色$a$的修改。

因此这道题就这样用带修改莫队轻松解决啦!

记得前面说的一些普通莫队与带修改莫队不同的地方就行了,比如分块的每一块的大小是$n^\frac{2}{3}$。这个很重要。。。

代码:

#include <bits/stdc++.h>
#define SZ (10005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,sqn,c[SZ],ct[SZ],c1,c2,mem[SZ][3],ans,tot[1000005],nal[SZ];
struct query
{
    int l,r,i,c;
    bool operator < (const query another)const
    {
        if(l/sqn==another.l/sqn)
        {
            if(r/sqn==another.r/sqn)return i<another.i;
            return r<another.r;
        }
        return l<another.l;
    }
}Q[SZ];
void add(int a){if(!tot[a])ans++;tot[a]++;}
void del(int a){tot[a]--;if(!tot[a])ans--;}
char opt[10];
int main()
{
    IN(n),IN(m),sqn=pow(n,(double)2/(double)3);
    for(int i=1;i<=n;i++)IN(c[i]),ct[i]=c[i];
    for(int i=1,a,b;i<=m;i++)
        if(scanf("%s",opt),IN(a),IN(b),opt[0]=='Q')
            Q[c1].l=a,Q[c1].r=b,Q[c1].i=c1,Q[c1].c=c2,c1++;
        else mem[c2][0]=a,mem[c2][1]=ct[a],mem[c2][2]=ct[a]=b,c2++;
    sort(Q,Q+c1),add(c[1]);
    int l=1,r=1,lst=0;
    for(int i=0;i<c1;i++)
    {
        for(;lst<Q[i].c;lst++)
        {
            if(l<=mem[lst][0]&&mem[lst][0]<=r)
                del(mem[lst][1]),add(mem[lst][2]);
            c[mem[lst][0]]=mem[lst][2];
        }
        for(;lst>Q[i].c;lst--)
        {
            if(l<=mem[lst-1][0]&&mem[lst-1][0]<=r)
                del(mem[lst-1][2]),add(mem[lst-1][1]);
            c[mem[lst-1][0]]=mem[lst-1][1];
        }
        for(++r;r<=Q[i].r;r++)add(c[r]);
        for(--r;r>Q[i].r;r--)del(c[r]);
        for(--l;l>=Q[i].l;l--)add(c[l]);
        for(++l;l<Q[i].l;l++)del(c[l]);
        nal[Q[i].i]=ans;
    }
    for(int i=0;i<c1;i++)printf("%d\n",nal[i]);
    return 0;
}

//因为本人太弱,所以可能讲得有点不到位,还请多多包涵。。。= ̄ω ̄=

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *