【数据结构】莫队（二）

　　今天的内容是带修莫队。@H_403_11@

例题：P1903 [国家集训队]数颜色 / 维护队列

题目描述

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：@H_403_11@

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。@H_403_11@

2、 R P Col 把第P支画笔替换为颜色Col。@H_403_11@

为了满足墨墨的要求，你知道你需要干什么了吗？@H_403_11@

输入格式

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。@H_403_11@

第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。@H_403_11@

第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。@H_403_11@

输出格式

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。@H_403_11@

输入输出样例

输入 #1

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

输出 #1

说明/提示

对于100%的数据，N≤50000，M≤50000，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。@H_403_11@

本题可能轻微卡常数@H_403_11@

来源：bzoj2120@H_403_11@

本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。@H_403_11@

带修莫队

　　莫队是一种很神奇的离线算法。可以解决区间上的问题，通过排序和对询问分块来优化暴力。@H_403_11@

　　普通的莫队题目都是给定的序列，不断的询问。@H_403_11@

　　那么如果在询问中夹杂了一些修改操作，莫队还能做吗？@H_403_11@

　　答案当然是可以的。@H_403_11@

　　回顾一下莫队的实现方法：@H_403_11@

　　　　1.提前预处理@H_403_11@

　　　　2.询问分块排序@H_403_11@

　　　　3.双指针移动求解。@H_403_11@

　　唯一会因为修改而产生变化的操作就是3操作。@H_403_11@

　　可以发现：当出现了修改操作之后，我当前询问处理的区间可能就不是我们本来要找的区间了。@H_403_11@

　　那么怎么办呢？@H_403_11@

　　借鉴一下可持久化线段树的思想：时光回溯。@H_403_11@

　　我们可以先把带修莫队当做一般的莫队来做，做完之后如果发现时间对不上就时光倒流。@H_403_11@

　　准确的说是：考虑两个时间点的操作之间的代价。@H_403_11@

　　这么说来，只要在普通莫队的一堆 while 循环后面再加两个就OK。@H_403_11@

 while(now<q[i].t)
     change(++now);
 while(now>q[i].t)
     change(now--);

代码

@H_403_11@

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=50005;
int col[N],n,m,sum[1000005],be[N];
int fans,qnum,cnum,ans[N];

struct qs{
    int l,r,t,id;
}q[N];
struct cs{
    int x,i;
}c[N];

bool cmp(qs x,qs y) {
    if(be[x.l]!=be[y.l])
        return x.l<y.l;
    if(be[x.r]!=be[y.r])
        return x.r<y.r;
    return x.t<y.t;
}

void upd1(int x) {
    if(!sum[col[x]])
        ++fans;
    ++sum[col[x]];
    return;
}

void upd2(int x) {
    --sum[col[x]];
    if(!sum[col[x]])
        --fans;
    return;
}

int l,now;

void change(int x) {
    if(c[x].i<=r&&c[x].i>=l) {
        --sum[col[c[x].i]];
        if(!sum[col[c[x].i]])
            --fans;
        if(!sum[c[x].x])
            ++fans;
        ++sum[c[x].x];
    }
    swap(c[x].x,col[c[x].i]);
    return;
}

int main()
{
    cin>>n>>m;
    int xx=pow(n,2.0/3.0);
    char opt; 
    for(int i=1;i<=n;i++) {
        cin>>col[i];
        be[i]=i/xx+1;
    }
    for(int i=1;i<=m;i++) {
        cin>>opt;
        if(opt==‘Q‘) {
            ++qnum;
            cin>>q[qnum].l>>q[qnum].r;
            q[qnum].t=cnum;
            q[qnum].id=qnum;
        }
        else {
            ++cnum;
            cin>>c[cnum].i>>c[cnum].x;
        }
    }
    sort(q+1,q+qnum+1,cmp);
    l=r=fans=now=0;
    for(int i=1;i<=qnum;i++) {
        while(l<q[i].l)
            upd2(l++);
        while(l>q[i].l)
            upd1(--l);
        while(r>q[i].r)
            upd2(r--);
        while(r<q[i].r)
            upd1(++r);
        while(now<q[i].t)
            change(++now);
        while(now>q[i].t)
            change(now--);
        ans[q[i].id]=fans;
    }
    for(int i=1;i<=qnum;i++)
        cout<<ans[i]<<endl;
    return 0;
}

数颜色