【SDOI2019】—世界地图（虚树+Kruscal）

传送门

直接每次暴力做是$qmnlog$的
考虑如果维护了地图前后缀的最小生成树
每次就相当于加入了$(m,1)$中间的$n$条边

加边就是找2点间最大值删去
考虑对最小生成树建虚树
对于前缀，对第一列的点建虚树，边权为链上最大值
后缀类似对最后一列这样做

这样每次合并就只需要对$O(n)$个点做最小生成树就可以了

复杂度$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<<'
';
	}
}