启发式合并&Manacher
启发式合并
概念：每一次合并利用贪心的思想把小的部分合并到大的部分之中，因为每一次合并后的区间大小一定会变为原来空间的两倍以上，所以时间复杂度为O(nlogn)。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10,M = 1e6+10;
int n,m,ans;
int head[M],idx;
struct Edge{
int next,to;
}edge[N];
int color[N],sz[M],p[M];
void add(int a,int b)
{
edge[idx]={head[a],b},head[a]=idx++;
sz[a]++;
}
void merge(int &x,int &y)
{
if(x==y) return;
if(sz[x]>sz[y]) swap(x,y);
for(int i=head[x];~i;i=edge[i].next)
{
int j=edge[i].to;
ans-=(color[j-1]==y)+(color[j+1]==y);
}
for(int i=head[x];~i;i=edge[i].next)
{
int j=edge[i].to;
color[j]=y;
if(edge[i].next==-1)
{
edge[i].next=head[y],head[y]=head[x];
break;
}
}
head[x]=-1;
sz[y]+=sz[x],sz[x]=0;
return;
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof head);
for(int i=1;i<=n;i++)
{
scanf("%d",&color[i]);
if(color[i]!=color[i-1]) ans++;
add(color[i],i);
}
for(int i=0;i<M;i++) p[i]=i;
while(m--)
{
int op;
scanf("%d",&op);
if(op==2) printf("%d\n",ans);
else{
int x,y;
scanf("%d%d",&x,&y);
merge(p[x],p[y]);
}
}
return 0;
}manacher
manacher算法解决的一般是回文串的问题，回文串长度必须是奇数，所以我们需要做一个初始化使他为奇数，我们从左向右遍历维护当前最长的回文串，设最长的回文串的中点为mid，右端点为mr，因此在遍历的时候，如果i<mr那么他的p[i]起点一定为min(p[2*mid-i],mr-i)，因为对称性，因为此算法的右端点一直是向右单调移动，所以时间复杂度为o(n)。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 3e7+10;
char a[N],b[N];
int n,p[N],len;
void init()
{
n=strlen(a);
b[len++]='^',b[len++]='#';
for(int i=0;i<n;i++) b[len++]=a[i],b[len++]='#';
b[len++]='$';
}
void manacher()
{
int mid,mr=0;
for(int i=1;i<len;i++)
{
if(i<mr) p[i]=min(p[2*mid-i],mr-i);
else p[i]=1;
while(b[i-p[i]]==b[i+p[i]]) p[i]++;
if(i+p[i]>mr) mr=p[i]+i,mid=i;
}
}
int main()
{
scanf("%s",a);
init();
manacher();
int res=0;
for(int i=1;i<len;i++) res=max(res,p[i]);
printf("%d\n",res-1);
return 0;
}
