cu求
by _SunLight_ @ 2022-10-06 15:47:57
@[_ChiFAN_](/user/520748)
change_old 不一定是a[x]
by xingke233 @ 2022-10-06 16:08:19
@[_ChiFAN_](/user/520748)
我的AC代码（友情注释版）：
```cpp
#include<bits/stdc++.h>
#define E 1e-9
#define INF 0x3f3f3f3f
#define LL long long
const int MOD=10007;
const int N=1000000+5;
const int dx[]= {-1,1,0,0};
const int dy[]= {0,0,-1,1};
using namespace std;
struct Node{
int l,r;//询问的左右端点
int time;//时间维度
int id;//询问的编号
}q[N];
struct Change{
int pos;//要修改的位置
int col;//要改成的值
}c[N];
int n,m,a[N];
int block;//分块
int numQ,numC;//查询、修改操作的次数
LL ans,cnt[N];
LL res[N];
bool cmp(Node a,Node b){//排序
return (a.l/block)^(b.l/block) ? a.l<b.l : ((a.r/block)^(b.r/block)?a.r<b.r:a.time<b.time);
}
void add(int x){//统计新的，根据具体情况修改
if(cnt[x]==0)
ans++;
cnt[x]++;
}
void del(int x){//减去旧的，根据具体情况修改
cnt[x]--;
if(cnt[x]==0)
ans--;
}
void change(int x,int ti){//改变时间轴
if(c[ti].pos>=q[x].l&&c[ti].pos<=q[x].r){
del(a[c[ti].pos]);//删除指定位置上的值
add(c[ti].col);//统计新的数
}
swap(c[ti].col,a[c[ti].pos]);//直接互换，下次执行时必定是回退这次操作
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
ans=0;
numQ=0;
numC=0;
memset(cnt,0,sizeof(cnt));
block=pow(n,0.66666);//分块
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
char op[10];
scanf("%s",op);
if(op[0]=='Q'){//查询操作
++numQ;//查询操作次数+1
scanf("%d%d",&q[numQ].l,&q[numQ].r);
q[numQ].id=numQ;//序号
q[numQ].time=numC;//时间轴
}
else{//修改操作
++numC;//修改操作次数+1
scanf("%d%d",&c[numC].pos,&c[numC].col);
}
}
sort(q+1,q+numQ+1,cmp);//对询问进行排序
int l=1,r=0,time=0;//左右指针与时间轴
for(int i=1;i<=numQ;i++){
int ql=q[i].l,qr=q[i].r;//询问的左右端点
int qtime=q[i].time;//询问的时间轴
while(l>ql) add(a[--l]);//[l-1,r,time]
while(l<ql) del(a[l++]);//[l+1,r,time]
while(r<qr) add(a[++r]);//[l,r+1,time]
while(r>qr) del(a[r--]);//[l,r-1,time]
while(time<qtime) change(i,++time);//[l,r,time+1]
while(time>qtime) change(i,time--);//[l,r,time-1]
res[q[i].id]=ans;//获取答案
}
for(int i=1;i<=numQ;i++)
printf("%lld\n",res[i]);
}
return 0;
}
```
by luqyou @ 2022-10-06 16:09:49
@[_ChiFAN_](/user/520748)
hack
```
6 5
1 1 9 4 5 5
Q 1 4
Q 2 6
R 1 9
R 1 8
Q 1 6
```
by xingke233 @ 2022-10-06 16:11:19
@[xingke233](/user/533452)
正确为
```
3
4
5
```
by xingke233 @ 2022-10-06 16:12:51
@[_ChiFAN_](/user/520748) 话说杨吃饭一改不缩进的习惯
by luqyou @ 2022-10-06 16:16:28
@[xingke233](/user/533452) 改了后我的代码还是存在问题
by _SunLight_ @ 2022-10-06 16:19:06
```
//6 5
//1 1 9 4 5 5
//Q 1 4
//Q 2 6
//R 1 9
//R 1 8
//Q 1 6
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[133334];
struct change{
int old,where,what;
}tim[133334];
struct question{
int l,r,t,d;
}s[133334];
int l1;
int l2;
char op;
int ans[133334];
int sum;
int f[1000001];
int sq;
bool cmp(question x,question y)
{
if(x.l/sq<y.l/sq)
return true;
if(x.l/sq>y.l/sq)
return false;
if(x.r<y.r)
return true;
if(x.r>y.r)
return false;
if(x.t<y.t)
return true;
else
return false;
}
void add(int x)
{
if(f[a[x]]==0)
sum++;
f[a[x]]++;
}
void del(int x)
{
if(f[a[x]]==1)
sum--;
f[a[x]]--;
}
void timeadd(int x,int left,int right)
{
if(tim[x].where>=left&&tim[x].where<=right)
{
if(f[a[tim[x].where]]==1)
sum--;
f[a[tim[x].where]]--;
if(f[tim[x].what]==0)
sum++;
f[tim[x].what]++;
}
a[tim[x].where]=tim[x].what;
}
void timedel(int x,int left,int right)
{
if(tim[x].where>=left&&tim[x].where<=right)
{
if(f[a[tim[x].where]]==1)
sum--;
f[a[tim[x].where]]--;
if(f[tim[x].old]==0)
sum++;
f[tim[x].old]++;
}
a[tim[x].where]=tim[x].old;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
scanf("%s",&op);
if(op=='Q')
{
l1++;
scanf("%d%d",&s[l1].l,&s[l1].r);
s[l1].t=l2;
s[l1].d=l1;
}
else
{
l2++;
scanf("%d%d",&tim[l2].where,&tim[l2].what);
tim[l2].old=a[tim[l2].where];
}
}
sq=sqrt(n);
sort(s+1,s+1+l1,cmp);
int L=1;
int R=0;
int T=0;
for(int i=1;i<=l1;i++)
{
while(L<s[i].l)del(L++);
while(L>s[i].l)add(--L);
while(R<s[i].r)add(++R);
while(R>s[i].r)del(R--);
while(T>s[i].t)timedel(T--,L,R);
while(T<s[i].t)timeadd(++T,L,R);
ans[s[i].d]=sum;
}
for(int i=1;i<=l1;i++)
{
printf("%d\n",ans[i]);
}
}
```
by _SunLight_ @ 2022-10-06 16:19:27
@[luqyou](/user/464732)
by _SunLight_ @ 2022-10-06 16:20:55
@[huanghaoxiang27](/user/713562)
不能用old记录，应该直接交换
by xingke233 @ 2022-10-06 16:21:49