当前位置: 首页> 文旅> 艺术 > 闵行区天气_gg模板网_山西网络营销seo_seo优化工作内容

闵行区天气_gg模板网_山西网络营销seo_seo优化工作内容

时间:2025/7/11 11:02:15来源:https://blog.csdn.net/summ1ts/article/details/142778879 浏览次数:0次
闵行区天气_gg模板网_山西网络营销seo_seo优化工作内容

原题链接

给你一个序列,多次询问 [ l , r ] [l,r] [l,r] 中出现的不同数的个数。这个我会!询问离线,然后树状数组——怎么还带修改?这个时候就要请出带修莫队了。

莫队算法可以以 O ( m n ) O(m\sqrt n) O(mn ) 的时间复杂度解决一些区间询问,支持离线的问题。带上修改操作也不难维护,只需要增加一个 t t t,表示该次询问前有几次修改,然后加上 t t t 指针的维护即可。排序时先按 l , r l,r l,r 排序,若 l , r l,r l,r 相等再按 t t t 从小到大排序。

接下来就是纯板子了,代码很好写的。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,m,a[N],cnt[N],res,ans[N],cnt1,cnt2,pos[N],vis[N];
struct node{int l,r,x,y,t,id;
}q1[N],q2[N];
bool cmp(node a,node b){if(pos[a.l]==pos[b.l]){if(pos[a.r]==pos[b.r]) return a.t<b.t;return pos[a.r]<pos[b.r];}return pos[a.l]<pos[b.l];
}
void del(int x){cnt[x]--;if(!cnt[x]) res--;
}
void add(int x){cnt[x]++;if(cnt[x]==1) res++;
}
void update(int i,int t){if(q1[i].l<=q2[t].x&&q1[i].r>=q2[t].x){//这次修改能够影响这个区间,我们才更改del(a[q2[t].x]),add(q2[t].y);}swap(a[q2[t].x],q2[t].y);
}
int main(){n=read(),m=read();int sz=pow(n,0.666);for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) pos[i]=(i-1)/sz+1;for(int i=1;i<=m;i++){char op;cin>>op;int x=read(),y=read();if(op=='Q') q1[++cnt1]={x,y,0,0,cnt2,i},vis[i]=1;else q2[++cnt2]={0,0,x,y,0,i};}sort(q1+1,q1+1+cnt1,cmp);for(int i=1,l=0,r=0,tt=0;i<=cnt1;i++){while(l<q1[i].l) del(a[l++]);while(r>q1[i].r) del(a[r--]);while(l>q1[i].l) add(a[--l]);while(r<q1[i].r) add(a[++r]);while(tt<q1[i].t) update(i,++tt);while(tt>q1[i].t) update(i,tt--);ans[q1[i].id]=res;}for(int i=1;i<=m;i++) if(vis[i]) cout<<ans[i]<<endl;return 0;
}
关键字:闵行区天气_gg模板网_山西网络营销seo_seo优化工作内容

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: