@[月见之免](/space/show?uid=81372) 带修改的块大小难道不是一般是$n^{\frac{2}{3}}$么?
by ecnerwaIa @ 2019-04-29 20:56:29
@[月见之免](/space/show?uid=81372) 还有我头一次见这种排序方式...
by ecnerwaIa @ 2019-04-29 21:06:44
@[千年之狐_天才](/space/show?uid=54113) 奇偶排序？
by guodong @ 2019-04-29 21:07:40
@[月见之免](/space/show?uid=81372) 为什么奇偶排序。。。
by ecnerwaIa @ 2019-04-29 21:08:07
@[月见之免](/space/show?uid=81372) 我帮你大改动一下
by ecnerwaIa @ 2019-04-29 21:10:22
@[月见之免](/space/show?uid=81372) 改完了
by ecnerwaIa @ 2019-04-29 21:13:28
```cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#define ri register int
using namespace std;
#define N 1000010
int ans,col[N],a[N],blo[N];
inline int gi()
{
register char tmp=getchar();
while(tmp>'9'||tmp<'0') tmp=getchar();
ri ans=0;
while(tmp<='9'&&tmp>='0')
{
ans=ans*10+tmp-'0';
tmp=getchar();
}
return ans;
}
int n,m,cntq,cntc,len;
struct Que{
int l,r,time,ans,pos;
}q[N];
struct Cha{
int v,pos;
}c[N];
bool pre(Que a1,Que b1)
{
if(blo[a1.l]!=blo[b1.l])return a1.l<b1.l;
if(blo[a1.r]!=blo[b1.r])return a1.r<b1.r;
return a1.time<b1.time;
}
inline void add(int pos)
{
if((++col[a[pos]])==1) ans++;
}
inline void del(int pos)
{
if((--col[a[pos]])==0) ans--;
}
inline void work(int pos,int l,int r)
{
int v=c[pos].v,loc=c[pos].pos;
if(v==a[loc]) return;
if(loc<=r&&loc>=l)
{
col[v]++;
col[a[loc]]--;
if(col[a[loc]]==0) ans--;
if(col[v]==1) ans++;
}
swap(c[pos].v,a[loc]);
}
bool cmp(Que a,Que b)
{
return a.pos<b.pos;
}
signed main()
{
n=gi(),m=gi();
for(ri i=1;i<=n;i++)
a[i]=gi();
for(ri i=1;i<=m;i++)
{
register char opt;
scanf(" %c",&opt);
if(opt=='Q')
{
q[++cntq].l=gi();
q[cntq].r=gi();
q[cntq].time=cntc;
q[cntq].pos=cntq;
}
else
{
c[++cntc].pos=gi();
c[cntc].v=gi();
}
}
len=pow(n,2.0/3);
for(int i=1;i<=n;++i)blo[i]=(i-1)/len+1;
sort(q+1,q+cntq+1,pre);
int l=0,r=0,now=0;
for(ri i=1;i<=m;i++)
{
int ql=q[i].l,qr=q[i].r,qt=q[i].time;
while(l<ql) del(l++);
while(l>ql) add(--l);
while(r<qr) add(++r);
while(r>qr) del(r--);
while(now<qt)
work(++now,ql,qr);
while(now>qt)
work(now--,ql,qr);
q[i].ans=ans;
}
sort(q+1,q+cntq+1,cmp);
for(ri i=1;i<=cntq;i++)
{
printf("%d\n",q[i].ans);
}
}
```
by ecnerwaIa @ 2019-04-29 21:13:39
当然如果要离散话也可以，但是不是你那样离散的
by ecnerwaIa @ 2019-04-29 21:14:05
这个我晚上要打比赛，就先下了，等10:35如果有问题再问我吧
by ecnerwaIa @ 2019-04-29 21:15:05
@[千年之狐_天才](/space/show?uid=54113) thx
by guodong @ 2019-04-29 21:22:41