带修改莫队

· · 个人记录

简介

一般莫队是不支持修改的，所以我们需要对普通莫队进行一些修改，让它支持修改。

没学过普通莫队算法的建议先学普通莫队算法

主要思想

莫队的移动

主要讲一讲和普通莫队不一样的地方，也就是带修莫队增加的地方

普通莫队只有 l 和 r 两轴，由于我们要支持修改，所以我们添加一个时间轴 t 来表示修改过的次数

那么每个询问就拥有三个属性 (l,r,t)

如果现在所在的点是 (l,r,t)，那么对于 t 轴，就有两个可移动的方向：

(l,r,t + 1)$ 和 $(l,r,t - 1)

然后每动一步就进行一次更改操作

先从一道例题 P1903 [国家集训队] 数颜色 / 维护队列 入手

假如用 CL,CR,CT 来表示上一次询问的 l,r,t，那么代码就变成了这样

while(CL > l) Add(a[--CL]);
while(CR < r) Add(a[++CR]); //普通莫队操作
while(CL < l) Delete(a[CL++]);
while(CR > r) Delete(a[CR--]);
while(CT < t) Upd(++CT,i); //改少了就改过去 
while(CT > t) Upd(CT--,i); //改多了就改回来
```cpp void Upd(int x,int id) //第x次更改，第id次询问 { if(change[x].num >= q[id].l&&change[x].num <= q[id].r) //如果即将更改的数在查询区间内，那就会对结果造成影响 { Delete(a[change[x].num]); //删除原数 Add(change[x].col); //添加新颜色 } swap(a[change[x].num],change[x].col); //第一次变成新颜色，第二次旧颜色，第三次新颜色......以此类推，每次都会更新或还原 } ``` ## 分块和排序 注：以下所有方法都没有证明，因为~~我不会~~没必要证明 首先，块长从 $\sqrt{n}$ 变为了 $n^{\frac{2}{3}}$，时间复杂度就变为了 $O(n^{\frac{3}{5}})

然后排序有三个关键字，即排序优先级从上到下

代码

上本题代码


#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

const int N = 133343;

const int M = 1000010;

struct Q //询问
{
    int l,r,t,id;
}q[N];

struct Change //更改
{
    int num,col;
}change[N];

int posi[N],a[N],t[M],ans[N];
int n,m,qnum,rnum,sum,sq; //qnum,rnum存储查询和修改的次数

const bool cmp(const Q& x,const Q& y)
{
    if(posi[x.l] != posi[y.l]) return posi[x.l] < posi[y.l];
    else if(posi[x.r] != posi[y.r]) return posi[x.r] < posi[y.r];
    else return x.t < y.t;
}

void Add(int x) //添加某颜色 
{
    if(t[x] == 0) sum++;
    t[x]++;
}

void Delete(int x) //删除某颜色 
{
    t[x]--;
    if(t[x] == 0) sum--;
}

void Upd(int x,int id) //第x次更改，第id次询问
{
    if(change[x].num >= q[id].l&&change[x].num <= q[id].r) //如果即将更改的数在查询区间内，那就会对结果造成影响
    {
        Delete(a[change[x].num]); //删除原数
        Add(change[x].col); //添加新颜色 
    }
    swap(a[change[x].num],change[x].col); //第一次变成新颜色，第二次旧颜色，第三次新颜色......以此类推，每次都会更新或还原
}

void MO()
{
    int i,CL = 1,CR = 0,CT = 0;
    for(i = 1;i <= qnum;i++)
    {
        int l = q[i].l,r = q[i].r,t = q[i].t;
        while(CL > l) Add(a[--CL]);
        while(CR < r) Add(a[++CR]); //普通莫队操作
        while(CL < l) Delete(a[CL++]);
        while(CR > r) Delete(a[CR--]);
        while(CT < t) Upd(++CT,i); //改少了就改过去 
        while(CT > t) Upd(CT--,i); //改多了就改回来
        ans[q[i].id] = sum;
    }
}

int main()
{
    int i;
    cin>>n>>m;
    sq = pow(n,2.0 / 3.0); //块长
    for(i = 1;i <= n;i++) cin>>a[i];
    for(i = 1;i <= n;i++) posi[i] = (i - 1) / sq + 1; //分块
    for(i = 1;i <= m;i++)
    {
        char op;
        cin>>op;
        if(op == 'Q')
        {
            qnum++;
            cin>>q[qnum].l>>q[qnum].r;
            q[qnum].t = rnum; //已经修改的次数 
            q[qnum].id = qnum;
        }
        else
        {
            rnum++;
            cin>>change[rnum].num>>change[rnum].col;
        }
    }
    sort(q + 1,q + qnum + 1,cmp);
    MO();
    for(i = 1;i <= qnum;i++) cout<<ans[i]<<endl;
    return 0;
}

完结撒花