bzoj 1483: [HNOI2009]梦幻布丁 （set）

题目描述

传送门

题解

这道题其实应该是splay的启发式合并，但是可以用set水啊。 时间复杂度是 O(nlogn) ，因为每次合并的时候是将元素少的加入到元素多的集合中，那么对于小集合来说长度每次其实都至少翻了两倍，最多翻 logn 次。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<set> #include<algorithm> #define N 1000003 using namespace std; int a[N],col[N],n,m,ans; set<int> t[N]; int main() { freopen("a.in","r",stdin); freopen("my.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); col[a[i]]=a[i]; t[a[i]].insert(i); } ans=1; for (int i=1;i<=n-1;i++) if (a[i]!=a[i+1]) ans++; for (int i=1;i<=m;i++){ int opt,x,y; scanf("%d",&opt); if (opt==2) printf("%d\n",ans); else { scanf("%d%d",&x,&y); swap(x,y); if (x==y) continue; if (t[col[x]].size()<t[col[y]].size()) swap(col[x],col[y]); x=col[x]; y=col[y]; set<int>::iterator j; for (j=t[y].begin();j!=t[y].end();j++) { if (t[x].find(*j-1)!=t[x].end()&&(*j-1)>=1) ans--; if (t[x].find(*j+1)!=t[x].end()&&(*j+1)<=n) ans--; } for (j=t[y].begin();j!=t[y].end();j++) t[x].insert(*j); t[y].clear(); } } }