- BZOJ
2120 RE60求助
- 2022-9-17 16:00:39 @
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read();
const int N=200005;
int pos[N],a[N],num[1000005],cntq,cntg,l,r,res,tim,ans[N],n,m,cnt;
char c;
struct node{
int l,r,ID,time;
bool operator < (const node &b)const{
return (pos[l]^pos[b.l])?pos[l]<pos[b.l]:(pos[r]^pos[b.r])?pos[r]<pos[b.r]:time<b.time;
}
}q[N];
struct note{
int wz,color;
}g[N];
void add(int w){
if(num[a[w]]==0) ++res;
++num[a[w]];
}
void sub(int w){
if(num[a[w]]==1) --res;
--num[a[w]];
}
signed main()
{
n=read();m=read();
cnt=pow(n,(double)2/(double)3);
for(int i=1;i<=n;++i) {
a[i]=read();
pos[i]=(i-1)/cnt+1;
}
for(int i=1;i<=m;++i){
cin>>c;
if(c=='R'){
g[++cntg].wz=read();
g[cntg].color=read();
}
else {
q[++cntq].l=read();
q[cntq].r=read();
q[cntq].time=cntg;
q[cntq].ID=cntq;
}
}
sort(q+1,q+1+cntq);
l=1;r=0;res=0;tim=0;
for(int i=1;i<=cntq;++i)
{
while(q[i].l<l) add(--l);
while(q[i].r>r) add(++r);
while(q[i].l>l) sub(l++);
while(q[i].r<r) sub(r--);
while(q[i].time>tim){
++tim;
if(q[i].l<=g[tim].wz&&q[i].r>=g[tim].wz)
{
if(num[a[g[tim].wz]]==1) --res;
--num[a[g[tim].wz]];
if(num[a[g[tim].color]]==0) ++res;
++num[a[g[tim].color]];
}
swap(a[g[tim].color],g[tim].color);
}
while(q[i].time<tim){
if(q[i].l<=g[tim].wz&&q[i].r>=g[tim].wz)
{
if(num[a[g[tim].color]]==1) --res;
--num[a[g[tim].color]];
if(num[a[g[tim].wz]]==0) ++res;
++num[a[g[tim].wz]];
}
--tim;
swap(a[g[tim].color],g[tim].color);
}
ans[q[i].ID]=res;
}
for(int i=1;i<=cntq;++i)
printf("%lld\n",ans[i]);
return 0;
}
inline int read(){
int x=0;int b=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') b=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x*b;
}
0 条评论
目前还没有评论...