[SDOI2019] - World Map (Virtual Tree + Kruscal)

Portal

Direct violence is qmnlogqmnlogqmnlog
Consider maintaining a minimum spanning tree with map prefixes and suffixes
Each time it is equivalent to adding (m,1)(m,1)(m,1) the middle of the nnn edge.

To add edges is to find the maximum between two points and delete them.
Consider building virtual trees for minimum spanning trees
For prefixes, virtual trees are constructed for the points in the first column, and the edge weight is the maximum in the chain.
Suffixes are similar to doing this for the last column

So each merge only needs to do the minimum spanning tree for O(n)O(n)O(n) O (n) points.

Complexity O(qnlogn+mnlogn)O(qnlogn+mnlogn)O(qnlogn+mnlogn)O(qnlogn+mnlogn)

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>
#define uint unsigned int 
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
uint SA,SB,SC;
int lim;
inline int rnd(){
	SA^=SA<<16,SA^=SA>>5,SA^=SA<<1;
   	uint t=SA;
    SA=SB,SB=SC,SC^=t^SA;
    return SC % lim + 1;
}
struct edge{
	int u,v,w;
	edge(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
	friend inline bool operator <(cs edge &a,cs edge &b){
		return a.w<b.w;
	}
};
cs int N=105,M=10005;
int ga[N*M];
inline int find(int x){
	return ga[x]==x?x:ga[x]=find(ga[x]);
}
struct mst{
	vector<edge> e;
	vector<int> pl,pr,p;
	ll anc;
	inline void build(cs vector<edge> &E,cs vector<int> &P){
		pl=pr=p=P,e=E;
		for(edge &x:e)anc+=x.w;
	}
}pre[M],suf[M],now[M];
int n,m,pos[N][M],tot;
vector<edge> e1[M],e2[M];
int tag[N*M];
ll anc;
vector<pii >e[N*M];
vector<edge> E;
vector<int> p,pp[M];
inline void addedge(int u,int v,int w){
	e[u].pb(pii(v,w)),e[v].pb(pii(u,w));
}
bool dfs(int u,int fa){
	int res=0;
	for(pii &x:e[u]){
		if(x.fi==fa)continue;
		res+=dfs(x.fi,u);
	}
	tag[u]|=(res>=2);
	res+=tag[u];
	return res;
}
void dfs2(int u,int fa,int last,int val){
	if(tag[u]){
		if(last)
		E.pb(edge(last,u,val));
		last=u,val=0,p.pb(u);
	}
	for(pii &x:e[u]){
		if(x.fi==fa)continue;
		dfs2(x.fi,u,last,max(val,x.se));
	}
	e[u].clear(),tag[u]=0;
}
inline mst merge(mst &a,mst &b,vector<edge> &Edge){
	mst c;anc=a.anc+b.anc;
	c.pl=a.pl,c.pr=b.pr;
	E.clear();
	for(edge &x:Edge)E.pb(x);
	for(edge &x:a.e)E.pb(x),anc-=x.w;
	for(edge &x:b.e)E.pb(x),anc-=x.w;
	sort(E.bg(),E.end());
	for(int &x:a.p)ga[x]=x,tag[x]=0;
	for(int &x:b.p)ga[x]=x,tag[x]=0;
	for(int &x:a.pl)tag[x]=1;
	for(int &x:b.pr)tag[x]=1;
	for(edge &x:E){
		int f1=find(x.u),f2=find(x.v);
		if(ga[f1]!=f2){
			ga[f1]=f2,addedge(x.u,x.v,x.w),anc+=x.w;
		}
	}
	E.clear(),p.clear();
	dfs(a.p[0],0);
	dfs2(a.p[0],0,0,0);
	c.e=E,c.p=p,c.anc=anc;
	return c;
}
int main(){
	n=read(),m=read(),SA=read(),SB=read(),SC=read(),lim=read();
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)pos[i][j]=++tot;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		int w=rnd();
		e1[j].pb(edge(pos[i][j],pos[i][j%m+1],w));
	}
	for(int i=1;i<n;i++)
	for(int j=1;j<=m;j++){
		int w=rnd();
		e2[j].pb(edge(pos[i][j],pos[i+1][j],w));
	}
	for(int j=1;j<=m;j++)for(int i=1;i<=n;i++)pp[j].pb(pos[i][j]);
	for(int i=1;i<=m;i++)
		now[i].build(e2[i],pp[i]);
	pre[1]=now[1];
	for(int i=2;i<=m;i++)pre[i]=merge(pre[i-1],now[i],e1[i-1]);
	suf[m]=now[m];
	for(int i=m-1;i;i--)suf[i]=merge(now[i],suf[i+1],e1[i]);
	int q=read();
	while(q--){
		int l=read(),r=read();
		cout<<(merge(pre[l-1],suf[r+1],e1[m])).anc<<'\n';
	}
}

Posted on Sun, 06 Oct 2019 03:38:22 -0700 by Prellyan