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

本文主要是介绍【洛谷P1903】【模板】分块/带修改莫队（数颜色），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门
题解：分块

//by sdfzchy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010,mod=1e9+7;
int n,m;
inline int in()
{char tmp=getchar();int res=0,f=1;while((tmp<'0'||tmp>'9')&&tmp!='-')tmp=getchar();if(tmp=='-') f=-1,tmp=getchar();while(tmp>='0'&&tmp<='9')   res=(res<<1)+(res<<3)+(tmp^48),tmp=getchar();return res*f;
}
int pre[N],head[N],siz,a[N],bel[N];
vector<int> v[N];
char s[10];int ask(int l,int r)
{int ans=0;for(int i=l;i<=min(r,bel[l]*siz);i++) if(pre[i]<l)               ans++;if(bel[l]==bel[r]) return ans;for(int i=(bel[r]-1)*siz+1;i<=r;i++)  if(pre[i]<l) ans++;for(int i=bel[l]+1;i<=bel[r]-1;i++)   ans+=lower_bound(v[i].begin(),v[i].end(),l)-v[i].begin();return ans; 
}
int b[N];void reset(int x)
{v[x].clear();for(int i=(x-1)*siz+1;i<=min(n,x*siz);i++) v[x].push_back(b[i]);sort(v[x].begin(),v[x].end());
}void change(int pos,int x)
{memset(head,0,sizeof(head));a[pos]=x;for(int i=1;i<=n;i++){b[i]=head[a[i]];head[a[i]]=i;}for(int i=1;i<=n;i++)if(pre[i]!=b[i])reset(bel[i]),i=bel[i]*siz;for(int i=1;i<=n;i++) pre[i]=b[i],b[i]=0;
}int main()
{n=in(),m=in();siz=sqrt(n);for(int i=1;i<=n;i++){a[i]=in();pre[i]=head[a[i]];head[a[i]]=i;bel[i]=(i-1)/siz+1;v[bel[i]].push_back(pre[i]);}for(int i=1;i<=bel[n];i++) sort(v[i].begin(),v[i].end());for(int i=1,x,y;i<=m;i++){scanf("%s",s);x=in(),y=in();if(s[0]=='Q') printf("%d\n",ask(x,y));else change(x,y);}return 0;   
}