HDU 5398(LCT)

HDU - 5398(LCT)

用LCT动态维护环

这题需要我们弄一些小性质

假设我们从大的数向小的数连边，那么一定是向大的数的因子连边，加入的边总数就是\(n\ln\)

如果这条边已经存在，那么就要从当前产生的环上换下来，存一个最小值

这样就是\(LCT\)模拟连边过程，总复杂度$n \cdot \log n \cdot \ln n $

#include<cstdio>
#include<cctype>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10;

int n=1e5;
vector <int> fac[N];
int fa[N],son[N][2];
int rev[N];
struct Node{
	int x,id;
	Node operator + (const Node t) const{
		Node res;
		res.x=min(x,t.x);
		if(res.x==x) res.id=id;
		else res.id=t.id;
		return res;
	}
} s[N],val[N];

inline int dir(int x){ return son[fa[x]][1]==x; }
inline int isroot(int x){ return !fa[x] || (son[fa[x]][0]!=x&&son[fa[x]][1]!=x); }

void Up(int u) {
	if(!u) return;
	s[u]=val[u];
	if(son[u][0]) s[u]=s[u]+s[son[u][0]];
	if(son[u][1]) s[u]=s[u]+s[son[u][1]];
}
void Down(int u) {
	if(!u||!rev[u]) return;
	int t;
	if(son[u][0]) {
		t=son[u][0];
		rev[t]^=1;
		swap(son[t][0],son[t][1]);
	}
	if(son[u][1]) {
		t=son[u][1];
		rev[t]^=1;
		swap(son[t][0],son[t][1]);
	}
	rev[u]=0;
}

int stk[N],top;
int eu[N],ev[N];

void rotate(int u) {
	int f=fa[u],ff=fa[f];
	Down(ff),Down(f),Down(u);
	int d=dir(u);
	fa[u]=ff; if(!isroot(f)) son[ff][dir(f)]=u;
	son[f][d]=son[u][!d]; fa[son[u][!d]]=f;
	fa[f]=u,son[u][!d]=f;
	Up(f),Up(u),Up(ff);
}

void Splay(int x) {
	Down(x),Up(x);
	static int stk[N],top=0;
	int t=x;
	while(!isroot(t)) stk[++top]=t,t=fa[t];
	stk[++top]=t;
	while(top) Down(stk[top--]);
	while(!isroot(x)) {
		int f=fa[x];
		if(!isroot(f)) {
			if(dir(x)^dir(f)) rotate(x);
			else rotate(f);
		}
		rotate(x);
	}
}



void Access(int x){ for(int t=0; x; t=x,x=fa[x]) Splay(x),son[x][1]=t,Up(x); }
void MakeRoot(int x) {
	Access(x);
	Splay(x);
	rev[x]^=1;
	swap(son[x][0],son[x][1]);
}

int GetRoot(int x) { 
	Access(x);
	Splay(x);
	do {
		Down(x);
		if(!son[x][0]) break;
		x=son[x][0];
	} while(1);
	Splay(x);
	return x;
}


void Cut(int x,int y) {
	MakeRoot(x);
	Access(y);
	Splay(x);
	fa[y]=0;
	son[x][1]=0;
	Up(x);
}


ll ans;
ll res[N];



void Link(int x,int y,int w) {
	if(GetRoot(x)==GetRoot(y)) {
		MakeRoot(x);
		Access(y);
		Node t=s[y];
		if(t.x>=w) return;
		ans-=t.x;
		Cut(eu[t.id],t.id);
		Cut(ev[t.id],t.id);
		son[t.id][0]=son[t.id][1]=fa[t.id]=rev[t.id]=0;
		stk[++top]=t.id;
	}
	MakeRoot(y);
	int t=stk[top--];
	fa[t]=rev[t]=0,son[t][0]=son[t][1]=0,s[t]=val[t]=(Node){w,t};
	eu[t]=x,ev[t]=y;
	ans+=w;
	fa[t]=x;
	fa[y]=t;
}



int main(){
	rep(i,n+1,2*n) stk[++top]=i;
	rep(i,1,n) s[i]=val[i]=(Node){(int)1e9,i};
	for(reg int i=1;i<=n;++i) for(reg int j=i+i;j<=n;j+=i) fac[j].push_back((int)i);
	rep(i,2,n) {
		drep(j,fac[i].size()-1,0) Link(i,fac[i][j],fac[i][j]);
		res[i]=ans;
	}
	while(~scanf("%d",&n)) printf("%lld\n",res[n]);
}