蒟蒻刚学带修莫队,满怀期望的交上去,结果五颜六色。 希望有大佬能帮我一下 QAQ
#include<bits/stdc++.h>
using namespace std;
#define isdigit(ch) (ch>='0'&&ch<='9')
#define int long long
const int maxn=1e6+7;
#define il inline
il void read(int &x)
{
x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
}
struct miku{
int l,r,id,t;
}q[maxn];
struct question{
int pos,col;
}c[maxn];
int n,m,a[maxn],cnt[maxn],now=0,l=1,r=0,t=0;
int bnum,size,belong[maxn],DFN,num,ans[maxn];
il bool cmp(miku a,miku b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.r]^belong[b.r])?belong[a.r]<belong[b.r]:a.t<b.t);
}
il void add(int pos)
{
if(!cnt[a[pos]]) ++now;
++cnt[a[pos]];
}
il void del(int pos)
{
--cnt[a[pos]];
if(!cnt[a[pos]]) --now;
}
il void change(int l,int r,int x)
{
int pos=c[x].pos,Col=c[x].col;
if(pos>=l&&pos<=r)
{
cnt[a[pos]]--;
if(!cnt[a[pos]]) now--;
if(!cnt[Col]) now++;
cnt[Col]++;
}
swap(a[pos],Col);
}
signed main()
{
// freopen("6.in","r",stdin);
// freopen("IA.out","w",stdout);
read(n),read(m);
size=pow(n,5.0/12);
bnum=ceil((double)n/size);
for(int i=1;i<=bnum;i++)
for(int j=(i-1)*size+1;j<=size*i;j++)
belong[j]=i;
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=m;i++)
{
char opt[5];
scanf("%s",opt);;
if(opt[0]=='Q')
{
++num;
read(q[num].l),read(q[num].r);
q[num].id=num,q[num].t=DFN;
}
if(opt[0]=='R')
{
++DFN;
read(c[DFN].pos),read(c[DFN].col);
}
}
sort(q+1,q+1+num,cmp);
for(int i=1;i<=num;i++)
{
int ql=q[i].l,qr=q[i].r,pos=q[i].id,qt=q[i].t;
while(l<ql) del(l++);
while(l>ql) add(--l);
while(r<qr) add(++r);
while(r>qr) del(r--);
while(t<qt) change(ql,qr,++t);
while(t>qt) change(ql,qr,t--);
ans[pos]=now;
}
for(int i=1;i<=num;i++) printf("%lld\n",ans[i]);
return 0;
}