莫队学习总结（二）

本文参考自：https://www.cnblogs.com/ouuan/p/MoDuiTutorial.html

带修莫队

普通莫队只能解决没有修改的问题，那么带修改的问题怎么解决？带修莫队就是一种支持单点修改的莫队算法。

算法简介

还是对询问进行排序，每次询问除了左端点和右端点还要记录这个询问是在第几次修改之后（时间），以左端点所在块为第一关键字，以右端点所在块为第二关键字，以时间为第三关键字进行排序。
暴力查询时，如果当前修改时间比询问时间的修改数少那就没修改的进行修改，反之回退。
需要注意的是，修改部分分为两部分：

1. 若修改的位置在当前区间内，需要更新答案（del原来的颜色，add修改后的颜色）
2. 无论修改的位置是否在当前区间内，都要进行修改（以供add和del函数在以后更新答案）

分块大小的选择以及复杂度

视作n==m的话，取 B = $n^{\frac{2}{3}}$ 时，复杂度 O(nlogn + $n^{\frac{2}{3}}$)。
例题1：P1903 [国家集训队]数颜色 / 维护队列
$O_2$才过的，它卡一点常数。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 2000000;
int n,m,nm;
int col[maxn],cnt[maxn],sum;
int ans[maxn];
struct Change{
    
    int p,col;
}c[maxn];
struct Query{
    
    int l,r,t;
    int id;
    bool operator < (Query& b){
    
        if(l/nm==b.l/nm){
    
            if(r/nm==b.r/nm)  return t < b.t;
            return r < b.r;
        }
        return l < b.l;
    }
}q[maxn];
void add(int x)
{
    
    if(cnt[x]==0)   sum++;
    cnt[x]++;
}
void del(int x)
{
    
    cnt[x]--;
    if(cnt[x]==0)   sum--;
}
void changx(int x,int ti)
{
    
    if(c[ti].p>=q[x].l&&c[ti].p<=q[x].r){
    
        del(col[c[ti].p]);
        add(c[ti].col);
    }
    swap(col[c[ti].p],c[ti].col);
}
int main(void)
{
    
    char cmd[4];
    scanf("%d%d",&n,&m);
    nm = pow(n,0.66666);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&col[i]);
    }
    int cntq,cntc,x,y;
    cntq = cntc = 0;
    for(int i=1;i<=m;i++){
    
        scanf("%s",cmd);
        if(cmd[0]=='Q'){
    
            cntq++;
            scanf("%d%d",&x,&y);
            q[cntq].id = cntq;
            q[cntq].l = x;q[cntq].r = y;
            q[cntq].t = cntc;
        }
        else{
    
            cntc++;
            scanf("%d%d",&x,&y);
            c[cntc].p = x;c[cntc].col = y;
        }
    }
    sort(q+1,q+cntq+1);
    int l = 2,r = 1,now = 0;
    for(int i=1;i<=cntq;i++){
    
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        while(now<q[i].t)
            changx(i,++now);
        while(now>q[i].t)
            changx(i,now--);
        ans[q[i].id] = sum;
    }
    for(int i=1;i<=cntq;i++){
    
        printf("%d\n",ans[i]);
    }
    return 0;
}

例题2：CF940F Machine Learning
题意翻译
给你一个数组$\{a_i\}$支持两种操作：
1、查询区间[l,r]中每个数字出现次数的mex。
2、单点修改某一个位置的值。
mex指的是一些数字中最小的未出现的自然数。值得注意的是，区间[l,r]总有数字是没有出现过的，所以答案不可能为0.
$n,Q\le 10^5$

注意一点，就是离散化原序列里的数字和修改的数字

	sort(pcol,pcol+tot);
    tot = unique(pcol,pcol+tot)-pcol;
    for(int i=1;i<=n;i++){
    
        col[i] = lower_bound(pcol,pcol+tot,col[i]) - pcol;
    }
    for(int i=1;i<=cntc;i++){
    
        c[i].col = lower_bound(pcol,pcol+tot,c[i].col) - pcol;
    }

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 2000000;
int n,m,nm;
int pcol[maxn],tot;
int col[maxn],cnt[maxn];
int ans[maxn],pcnt[maxn];
int cntq,cntc,x,y;
int l = 1,r = 0,now = 0;
struct Change{
    
    int p,col;
}c[maxn];
struct Query{
    
    int l,r,t;
    int id;
    bool operator < (Query& b){
    
        if(l/nm==b.l/nm){
    
            if(r/nm==b.r/nm)  return t < b.t;
            return r < b.r;
        }
        return l < b.l;
    }
}q[maxn];
inline void add(int x)
{
    
    pcnt[cnt[x]]--;
    cnt[x]++;
    pcnt[cnt[x]]++;

}
inline void del(int x)
{
    
    pcnt[cnt[x]]--;
    cnt[x]--;
    pcnt[cnt[x]]++;
}
inline void changx(int x,int ti)
{
    
    if(c[ti].p>=q[x].l&&c[ti].p<=q[x].r){
    
        del(col[c[ti].p]);
        add(c[ti].col);
    }
    swap(col[c[ti].p],c[ti].col);
}
int main(void)
{
    
    int cmd;
    scanf("%d%d",&n,&m);
    nm = pow(n,2.0/3);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&col[i]);
        pcol[tot++] = col[i];
    }
    for(int i=1;i<=m;i++){
    
        scanf("%d%d%d",&cmd,&x,&y);
        if(cmd==1){
    
            cntq++;
            q[cntq].id = cntq;
            q[cntq].l = x;q[cntq].r = y;
            q[cntq].t = cntc;
        }
        else{
    
            cntc++;
            c[cntc].p = x;c[cntc].col = y;
            pcol[tot++] = y;
        }
    }
    
    sort(pcol,pcol+tot);
    tot = unique(pcol,pcol+tot)-pcol;
    for(int i=1;i<=n;i++){
    
        col[i] = lower_bound(pcol,pcol+tot,col[i]) - pcol;
    }
    for(int i=1;i<=cntc;i++){
    
        c[i].col = lower_bound(pcol,pcol+tot,c[i].col) - pcol;
    }
    
    sort(q+1,q+cntq+1);
    for(int i=1;i<=cntq;i++){
    
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        while(now<q[i].t)
            changx(i,++now);
        while(now>q[i].t)
            changx(i,now--);
        for(ans[q[i].id]=1;pcnt[ans[q[i].id]]>0;++ans[q[i].id]);
    }
    for(int i=1;i<=cntq;i++){
    
        printf("%d\n",ans[i]);
    }
    return 0;
}