@[porse](/user/528926) 高某
把数组开大能过40分，但是有T的
by lovely_hyzhuo @ 2023-08-10 09:50:38
@[porse](/user/528926) TLE我帮不了你，是你代码问题
by lovely_hyzhuo @ 2023-08-10 09:52:53
@[porse](/user/528926)
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
int l,r;
int id;
int t;
}a[9000010];
int n,m,k;
struct node2
{
int pos,val;
}C[1000010];
int cnt[9000010];
int pos[9000010];
int sum;
int t;
int c[1900010];
void add(int col)
{
if(++cnt[col]==1)sum++;
}
void cel(int col)
{
if(--cnt[col]==0)sum--;
}
void work(int now,int i)
{
if(C[now].pos>=a[i].l&&C[now].pos<=a[i].r)
{
if(--cnt[c[C[now].pos]]==0)sum--;
if(++cnt[C[now].val]==1)sum++;
}
swap(C[now].val,c[C[now].pos]);
}
bool cmp(node x,node y)
{
if(pos[x.l]==pos[y.l])
{
if (pos[x.r]==pos[y.r])
return x.t<y.t;
else
return x.r<y.r;
}
return pos[x.l]<pos[y.l];
}
int ans[1000010];
signed main()
{
cin>>n>>m;
t=pow(n,0.666);
for(int i=1;i<=n;i++)
cin>>c[i],pos[i]=(i+t-1)/t;
//for(int i=1;i<=n;i++)
// add(c[i]);
int qnum=0,cnum=0;
for(int i=1;i<=m;i++)
{
char op;
cin>>op;
int l,r;
cin>>l>>r;
if(op=='Q')
{
a[++qnum].l=l,a[qnum].r=r;
a[qnum].id=qnum,a[qnum].t=cnum;
}
else
C[++cnum].pos=l,C[cnum].val=r;
}
sort(a+1,a+qnum+1,cmp);
int l=1,r=0,now=0;
for(int i=1;i<=qnum;i++)
{while(l<a[i].l)cel(c[l++]);
while(l>a[i].l)add(c[--l]);
while(r<a[i].r)add(c[++r]);
while(r>a[i].r)cel(c[r--]);while(now<a[i].t)work(++now,i);
while(now>a[i].t)work(now--,i);
//cout<<ans[a[i].id]<<endl;
ans[a[i].id]=sum;
}
for(int i=1;i<=qnum;i++)
cout<<ans[i]<<endl;
return 0;
}
```
by lovely_hyzhuo @ 2023-08-10 10:11:08
你玩不玩原神（意思自己悟）
by porse @ 2023-08-10 10:52:08