题解 P1903 【【模板】分块/带修改莫队（数颜色）】

· · 题解

难受了一晚上，今天在做这道题突然醒悟，发现这种修改分块还是比较好维护的（因为太暴力，直接删掉重新统计）

推荐做这道题之前，看一下这个视频，讲的很好，码风也很好https://www.bilibili.com/video/av6445624/?from=search&seid=8442394378288027735

假设各位理解了那几个分块常用变量之后，我们就可以说一下这道题的核心之处，在我的代码里是a数组，b数组，pre数组和srt数组。

a【i】代表第i个小球的颜色，那么pre【i】就代表颜色i的上一个小球的位置（因为查询一个区间的时候，只需要判断每一个小球的上一个同颜色小球的位置是否在区间内，即大于区间左端点，大于则出现了两次，否则这个颜色的球在区间内是第一次出现），b【i】是通过pre数组得到的，通过pre不断更新，所以b【i】记录下来颜色i的上一个小球的位置，然后srt数组是分块的核心——他是在每一块内排序后的b数组，这样在整块内二分，就可以直接找到query想要的答案

逻辑关系是：a【i】通过pre【i】得到b【i】然后得到有用的srt【i】，这样做的好处是，修改a【i】的时候，我们可以重新暴力统计这几个数组，得到新的srt【i】，代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
const int sqrtn=1e3+10;
int block,num,l[sqrtn],r[sqrtn],belong[maxn],n,m,a[maxn],b[maxn],pre[maxn],srt[maxn];
void build()//初始化分块
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1,srt[i]=b[i];
    for(int i=1;i<=num;i++)
        sort(srt+l[i],srt+r[i]+1);
}
int bsearch(int L,int R,int x)//二分整块内，二分srt数组
{
    int i=L,j=R;
    while(i<=j)
    {
        int m=(i+j)>>1;
        if(srt[m]<x)
            i=m+1;
        else
            j=m-1;
    }
    return i-L;
}
int query(int L,int R)
{
    int ans=0;
    if(belong[L]==belong[R])
    {
        for(int i=L;i<=R;i++)
            if(b[i]<L)
                ans++;
        return ans;
    }
    for(int i=L;i<=r[belong[L]];i++)
        if(b[i]<L)
            ans++;
    for(int i=l[belong[R]];i<=R;i++)    
        if(b[i]<L)
            ans++;
    for(int i=belong[L]+1;i<=belong[R]-1;i++)
        ans+=bsearch(l[i],r[i],L);
    return ans;
}
void reset(int blk)//调整块内
{
    for(int i=l[blk];i<=r[blk];i++)
        srt[i]=b[i];
    sort(srt+l[blk],srt+r[blk]+1);
} 
void modify(int pos,int key)//暴力修改，重新统计 
{
    memset(pre,0,sizeof(pre)); 
    a[pos]=key;//在这里统一修改,这道题可以改成区间修改，只需要在这里全部修改完，然后重新统计pre数组 
    for(int i=1;i<=n;i++)
    {
        if(b[i]!=pre[a[i]])
        {
            b[i]=pre[a[i]];
            reset(belong[i]);//重新统计时，可以找到不同的b，这样就可以找到要修改的块，从而更新出来正确的srt数组
        }
        pre[a[i]]=i;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=pre[a[i]];
        pre[a[i]]=i;
    }
    build();
    char ch;
    for(int i=1,x,y;i<=m;i++)
    {
        scanf(" %c%d%d",&ch,&x,&y);
        if(ch=='Q')
        {
            printf("%d\n",query(x,y));
        }
        else if(ch=='R')
        {
            modify(x,y);
        }
    }
}