P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

有一说一，雨天的尾巴我其实骂了很久。主要是题面之前一直没耐心读，然后后面在其他地方看到了形式化题意，就做掉了。

其实感觉有很多题都比这玩意适合当板子，所以这个迟到的板子就是走个流程，反正权值线段树早就被我娶过门了（？

const ll maxn=1e5+5,maxv=1e9;
ll fa[maxn][18],dep[maxn];
struct node{
	ll id,val,ls,rs;
}t[maxn*50];
vector<ll>e[maxn];
ll tot;
unordered_map<ll,ll>mp;
ll id[maxn],cnt;
ll get_id(ll x){
	if(mp.count(x))return mp[x];
	id[++cnt]=x;
	return mp[x]=cnt;
}
#define mid ((l+r)>>1)
node upd(node it,node x,node y){
	if(x.id>y.id)swap(x,y);
	if(x.val<y.val)it.id=y.id,it.val=y.val;
	else it.id=x.id,it.val=x.val;
	return it;
}
void insert(ll x,ll l,ll r,ll k,ll ty){
	if(l==r){
		t[x].id=l;
		t[x].val+=ty;
		return ;
	}
	if(k<=mid){
		if(!t[x].ls)t[x].ls=++tot;
		insert(t[x].ls,l,mid,k,ty);
	}
	else {
		if(!t[x].rs)t[x].rs=++tot;
		insert(t[x].rs,mid+1,r,k,ty);
	}
	t[x]=upd(t[x],t[t[x].ls],t[t[x].rs]);
}
void merge(ll x,ll y,ll l,ll r){
	if(l==r){
		t[x].val+=t[y].val;
		return ;
	}
	if(t[x].ls){if(t[y].ls)merge(t[x].ls,t[y].ls,l,mid);}
	else {if(t[y].ls)t[x].ls=t[y].ls;}
	if(t[x].rs){if(t[y].rs)merge(t[x].rs,t[y].rs,mid+1,r);}
	else {if(t[y].rs)t[x].rs=t[y].rs;}
	t[x]=upd(t[x],t[t[x].ls],t[t[x].rs]);
}
ll n,m;
void dfs(ll x){
	dep[x]=dep[fa[x][0]]+1;
	for(ll i=1;i<=17;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		if(!fa[x][i])break;
	}
	for(auto v:e[x]){
		if(v==fa[x][0])continue;
		fa[v][0]=x;
		dfs(v);
	}
}
ll query(ll x,ll y){
	if(dep[x]<dep[y])swap(x,y);
	for(ll i=17;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	}
	if(x==y)return x;
	for(ll i=17;i>=0;i--){
		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
ll ans[maxn];
ll mx;
void work(ll x){
	for(auto v:e[x]){
		if(v==fa[x][0])continue;
		work(v);
		merge(x,v,1,mx);
	}
	ans[x]=(t[x].val!=0?id[t[x].id]:0);
}
struct dat{
	ll x,y,z;
	friend bool operator < (const dat &u,const dat &v){
		return u.z<v.z;
	} 
}q[maxn];
void solve(){
	n=R,m=R;
	mx=m;
	for(ll i=1;i<n;i++){
		ll x=R,y=R;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	tot=n;
	dfs(1);
	for(ll i=1;i<=m;i++){
		q[i].x=R,q[i].y=R,q[i].z=R;
	}
	sort(q+1,q+1+m);
	for(ll i=1;i<=m;i++){
		ll x=q[i].x,y=q[i].y,z=q[i].z;
		z=get_id(z);
		ll lca=query(x,y);
		insert(x,1,mx,z,1);
		insert(y,1,mx,z,1);
		insert(lca,1,mx,z,-1);
		if(lca)insert(fa[lca][0],1,mx,z,-1);
	}
	work(1);
	for(ll i=1;i<=n;i++)we(ans[i]);
	return ;
}

注意离散化值域来压缩空间。

原文地址：http://www.cnblogs.com/rnfmabj/p/luogup4556.html