题目链接

思路

这道题可以用分块，可以用莫队，可以用数结……

然而我只会分块和莫队耶

分块

首先来讲一下分块的思路：

每个点记录一个prepre代表这个颜色上一次出现的地点，显然[L,R][L,R]中pre<Lpre<L的就是第一次出现的颜色。

将数列分块，每一块块内排序，这样查询时只需二分寻找pre<Lpre<L的点。

BZOJ交不过耶，是不是我常数太大了qwq

分块代码

#pragma GCC optimize(2)//然而强制开O2也救不了我的大常数#include 
    
     #include 
     
      #include 
      
       #include 
       
        const int maxn=10000;const int maxc=1000000;int belong[maxn+10],n,m,color[maxn+10],size;int pre[maxn+10],nowc[maxc+10],r[maxn+10];int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}int main(){  n=read();  m=read();  size=(int)sqrt(n);  for(register int i=1; i<=n; ++i)    {      color[i]=read();      belong[i]=(i-1)/size+1;    }  for(register int i=1; i<=n; ++i)    {      r[i]=pre[i]=nowc[color[i]];      nowc[color[i]]=i;    }  int k=n/size;  for(register int i=1; i<=k; ++i)    {      std::sort(r+(i-1)*size+1,r+i*size+1);    }  if(n%size!=0)    {      std::sort(r+(n-n%size)+1,r+n+1);    }  while(m--)    {      char ch=getchar();      while((ch!='Q')&&(ch!='R'))        {          ch=getchar();        }      int a,b;      scanf("%d%d",&a,&b);      if(ch=='Q')        {          int ans=0;          if(belong[a]==belong[b])            {              for(register int i=a; i<=b; ++i)                {                  if(pre[i]
        
         n)                {                  be=n;                }              for(register int i=a; i<=be; ++i)                {                  if(pre[i]
        
       
      
     
    

莫队

这不就是裸的带修改莫队吗？（而且时间复杂度和常数似乎都优越一些耶）

莫队代码

#include 
    
     #include 
     
      #include 
      
       const int maxn=10000;const int maxc=1000000;struct query{  int l,r,t,id;};int belong[maxn+10],n,m,color[maxn+10];int nowl,nowr,nowt,ans[maxn+10],cntq,cntm,used[maxc+10],nowans;int pos[maxn+10],prec[maxn+10],nowc[maxn+10];query q[maxn+10];bool cmp(const query &a,const query &b){  if(belong[a.l]==belong[b.l])    {      if(belong[a.r]==belong[b.r])        {          return a.t
       
        q[x].t)    {      change_time(pos[nowt],prec[nowt]);      --nowt;    }  while(nowl
        
         q[x].l)    {      modify(--nowl,1);    }  while(nowr
         
          q[x].r) { modify(nowr--,-1); } ans[q[x].id]=nowans; return 0;}int main(){ scanf("%d%d",&n,&m); for(register int i=1; i<=n; ++i) { scanf("%d",&color[i]); } for(register int i=1; i<=m; ++i) { char ch[10]; int a,b; scanf("%s%d%d",ch,&a,&b); if(ch[0]=='Q') { q[++cntq].l=a; q[cntq].r=b; q[cntq].t=cntm; q[cntq].id=cntq; } else { pos[++cntm]=a; prec[cntm]=color[a]; nowc[cntm]=b; color[a]=b; } } int size=(int)sqrt(cntq); for(register int i=1; i<=n; ++i) { belong[i]=(i-1)/size+1; } std::sort(q+1,q+cntq+1,cmp); nowl=nowr=nowans=used[color[1]]=1; nowt=cntm; for(register int i=1; i<=cntq; ++i) { solve(i); } for(register int i=1; i<=cntq; ++i) { printf("%d\n",ans[i]); } return 0;}