2019.7.8 义乌模拟赛 T2 B
2021/7/9 6:35:49
本文主要是介绍2019.7.8 义乌模拟赛 T2 B,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
我们发现每个值的贡献其实是独立的。
所以这启发我们对于每个值单独计算。
题目中真正有意义的合并只有\(O(n)\)次,每次暴力归并所以是\(O(n^2+m)\)的。
但是这个显然不够优。
我们考虑启发式合并。
这样再用个set维护就可以了。时间复杂度\(O(nlog^2n)\)
用线段树合并可以一只log
code:
#include<bits/stdc++.h> #include<set> #define I inline #define re register #define Me(x,y) memset(x,y,sizeof(x)) #define N 300000 #define M 200000 #define W 200000 #define db double #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define it iterator using namespace std; int n,m,siz[N+5],x,y,z,un,wn,l,r,mid,A[N+5],Maxn[N+5],fa[N+5],cnt,ans=2147483647;set<int> C[N+5];set<int>::it now,pus;map<int,int> G; I void Make(int &x){!G[x]&&(G[x]=++cnt);x=G[x];} I void swap(int &x,int &y){x^=y^=x^=y;} I void read(int &x){ char s=getchar();x=0;while(s<'0'||s>'9') s=getchar(); while(s>='0'&&s<='9') x=x*10+s-48,s=getchar(); } int main(){ freopen("b.in","r",stdin);freopen("b.out","w",stdout); re int i;scanf("%d%d",&n,&m);for(i=1;i<=n;i++) read(A[i]),Make(A[i]),C[A[i]].insert(i),siz[A[i]]++,Maxn[A[i]]&&(ans=min(ans,i-Maxn[A[i]])),Maxn[A[i]]=i; for(i=1;i<=n+2*m;i++) fa[i]=i; while(m--){ read(x);read(y);Make(x);Make(y);if(x==y) {printf("%d\n",ans);continue;} un=fa[x];wn=fa[y];if(siz[un]>siz[wn]) swap(un,wn);for(now=C[un].begin();now!=C[un].end();now++){ z=*now;pus=C[wn].lower_bound(z);if(pus!=C[wn].end()) ans=min(ans,(*pus)-z); if(pus!=C[wn].begin()) --pus,ans=min(ans,z-*pus); C[wn].insert(z); }C[un].clear();fa[x]=un;fa[y]=wn;siz[wn]+=siz[un];siz[un]=0;printf("%d\n",ans); } }
这篇关于2019.7.8 义乌模拟赛 T2 B的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)