后面6个全T了,求帮忙卡常QwQ
Code:
#include<algorithm>
#include<iostream>
#include<cmath>
const int M=1e6+5;
int n,m,L,R,now,ans,cnt1,cnt2;
int a[M],qwq[M],pst[M],val[M],color[M];
struct sec
{
int L,R,t,bl,num;
friend bool operator<(const sec&a,const sec&b)
{
return a.bl==b.bl?a.R<b.R:a.L<b.L;
}
}s[M];
inline void swap(int&x,int&y){x^=y^=x^=y;}
inline void Add(int v){if(++a[v]==1)++ans;}
inline void Del(int v){if(--a[v]==0)--ans;}
inline void Wrk(int v)
{
if(L<=pst[v]&&pst[v]<=R)Del(color[pst[v]]),Add(val[v]);
swap(color[pst[v]],val[v]);
}
inline int read()
{
char s;int f=1,n=0;while(!isdigit(s=getchar()))if(s==45)f=-1;
while(n=n*10+(s^48),isdigit(s=getchar()));return f*n;
}
inline void write(int n)
{
char s[105];int top=0;while(s[++top]=n%10+'0',n/=10);
while(putchar(s[top--]),top);
}
signed main()
{
n=read();m=read();
int i,p=sqrt(n);
for(i=1;i<=n;++i)color[i]=read();
for(i=1;i<=m;++i)
{
char ch;
std::cin>>ch;
if(ch=='Q')
{
s[++cnt1].num=cnt1;
s[cnt1].L=read();s[cnt1].R=read();
s[cnt1].bl=s[cnt1].L/p;s[cnt1].t=cnt2;
}
if(ch=='R')
{
++cnt2;
pst[cnt2]=read();val[cnt2]=read();
}
}
std::sort(s+1,s+cnt1+1);
for(i=1;i<=cnt1;++i)
{
int l=s[i].L,r=s[i].R;
while(L<l)Del(color[L++]);
while(R<r)Add(color[++R]);
while(L>l)Add(color[--L]);
while(R>r)Del(color[R--]);
while(now<s[i].t)Wrk(++now);
while(now>s[i].t)Wrk(now--);
qwq[s[i].num]=ans;
}
for(i=1;i<=cnt1;++i)write(qwq[i]),putchar(10);
}