wyy,jbl
by _Pepsi_ @ 2023-08-09 11:54:45
@[_Pepsi_](/user/754310) 人家发求助帖为啥 wyy,我看你的回复才 wyy
by Disjoint_cat @ 2023-08-09 13:40:35
@[Donotplaygame](/user/549499) 正确的,赞同,@[_Pepsi_](/user/754310) 这人就深井冰
by _Pepsi_ @ 2023-08-09 14:13:55
正确的,中肯的
by _7Mr @ 2023-08-09 17:18:25
就是now出了问题,now不能作为答案返回 要重开一个变量记录答案好吧,而且你的那个排序有问题,带修莫队排序不一样,可以上网查查,size最好开成2000(手动开)
by dkh2007 @ 2023-08-10 16:39:12
@[dkh2007](/user/758766) 这些地方都没有问题吧
by Darling_zero_two @ 2023-08-12 11:54:44
@[Darling_zero_two](/user/754502) 你改一下试试还有后面几个都是优化
by dkh2007 @ 2023-08-12 14:38:44
```
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=133333+10,M=1e6+10;
LL a[N],cnt[M],tmp,pos[N],ans[N];
struct query
{
LL l,r,id;
LL tim;
}q[N];
int cntq;
bool cmp(query x,query y)
{
if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
if(pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];
return x.tim<y.tim;
}
struct change
{
LL col,p;
}c[N];
int cntc;
void del(LL x)
{
if(--cnt[a[x]]==0) tmp--;
}
void add(LL x)
{
if(++cnt[a[x]]==1) tmp++;
}
void work(LL now,LL i)
{
if(q[i].l<=c[now].p&&c[now].p<=q[i].r)
{
cnt[a[c[now].p]]--;
if(!cnt[a[c[now].p]]) tmp--;
cnt[c[now].col]++;
if(cnt[c[now].col]==1) tmp++;
}
swap(a[c[now].p],c[now].col);
}
int main()
{
int n,m;
cin>>n>>m;
int len=2000;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) pos[i]=(i-1)/len+1;
for(int i=1;i<=m;i++)
{
char op;
cin>>op;
if(op=='Q')
{
LL l,r;
cin>>l>>r;
q[++cntq].l=l,q[cntq].r=r,q[cntq].id=cntq;
q[cntq].tim=cntc;
}
else if(op=='R')
{
int p,col;
cin>>p>>col;
c[++cntc].p=p;
c[cntc].col=col;
}
}
sort(q+1,q+1+cntq,cmp);
LL l=1,r=0;
LL now=0;
for(int i=1;i<=m;i++)
{
while(l<q[i].l) del(l++);
while(r<q[i].r) add(++r);
while(l>q[i].l) add(--l);
while(r>q[i].r) del(r--);
while(now<q[i].tim) work(++now,i);
while(now>q[i].tim) work(now--,i);
ans[q[i].id]=tmp;
}
for(int i=1;i<=cntq;i++) cout<<ans[i]<<endl;
return 0;
}
```
看看我的,感觉和你的差不多,AC的
by dkh2007 @ 2023-08-12 14:41:06
@[dkh2007](/user/758766) 我的now就是你的tmp吧
by Darling_zero_two @ 2023-08-12 15:01:25
```
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=133333+10,M=1e6+10;
struct node
{
LL l,r,id,t;
}qq[N];
struct node1
{
LL pla,col;
}qr[N];
LL cntq,cntr;
LL n,m,a[N];
LL size,belong[N];
LL ans[N];
LL cnt[M],l=1,r,t;
LL now;
bool cmp(node x,node y)
{
if(belong[x.l]!=belong[y.l]) return belong[x.l]<belong[y.l];
if(belong[x.r]!=belong[y.r]) return belong[x.r]<belong[y.r];
return x.t<y.t;
}
void add(LL x)
{
if(++cnt[a[x]]==1) ++now;
}
void del(LL x)
{
if(--cnt[a[x]]==0)
--now;
}
void update(LL x,LL y)
{
if(qq[x].l<=qr[y].pla&&qq[x].r>=qr[y].pla)
{
cnt[a[qr[y].pla]]--;
if(!cnt[a[qr[y].pla]]) now--;
cnt[qr[y].col]++;
if(cnt[qr[y].col]==1) now++;
}
swap(a[qr[y].pla],qr[y].col);
}
int main()
{
cin>>n>>m;
size=2000;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
belong[i]=(i-1)/size+1;
for(int i=1;i<=m;i++)
{
char op;
LL x,y;
cin>>op>>x>>y;
if(op=='Q')
{
qq[++cntq].l=x;
qq[cntq].r=y;
qq[cntq].id=cntq;
qq[cntq].t=cntr;
}
else if(op=='R')
{
qr[++cntr].pla=x;
qr[cntr].col=y;
}
}
sort(qq+1,qq+cntq+1,cmp);
for(int i=1;i<=cntq;i++)
{
while(l<qq[i].l)
del(l++);
while(r<qq[i].r)
add(++r);
while(l>qq[i].l)
add(--l);
while(r>qq[i].r)
del(r--);
while(t<qq[i].t)
update(i,++t);
while(t>qq[i].t)
update(i,t--);
ans[qq[i].id]=now;
}
for(int i=1;i<=cntq;i++)
cout<<ans[i]<<endl;
return 0;
}
```
给你调过了
就是update那里传参数传错了
by dkh2007 @ 2023-08-12 16:37:00