题目大意：
给出一个有 \(n\) 行 \(m\) 列的网格图，第一列和最后一列是相连的，每条边都有对应的权值。
有 \(q\) 组询问，每次会给出 \(l_i\) 和 \(r_i\)，表示第 \(l_i\) 列至第 \(r_i\) 列上所有的点不能经过，求使除此之外所有点连通或间接连通的最小总权值。
对于 \(100\%\) 的数据，\(n \le 100\)，\(m \le 10^4\)，\(n \times q \le 10^6\)。
思路：
显然每组询问都是在求一棵只经过需求的点的最小生成树，但是如果就这样直接求解，时间复杂度会来到 \(O(qnm \log(nm))\)，一看就非常不可做，想到 LCT 动态维护最小生成树。但如果直接维护，显然也是会喜得 TLE。看到 \(n\) 的范围和网格图，尝试考虑对于每一列的最小生成树做前缀和与后缀和，最后询问时再通过第一列和最后一列相连的边来合并。但记下前缀最小生成树的整棵树，不 MLE 也会 TLE。此时我们还要深究网格图的特性。可以发现，对于新合并的两棵最小生成树，新的最小生成树只可能对于左边 MST 的最右一列与右边的 MST 的最左一列两点之间的路径长产生影响。对于其他的树边，完全不会有任何改变。
嗯？只跟关键点有关系，无法存下整棵树，这跟虚树的应用场景简直完美匹配！于是可以把最左边和最右边的两列作为关键点，做虚树前缀。那虚树的边权应该怎么定呢？考虑 LCT 如何动态维护最小生成树。对于新加入的边，尝试替换这条边两点间路径上权值最大的一条边。合并最小生成树时也是这样，所以只要记下关键点之间的路径的最大边，其它边累加即可。然而这里只需要边权的信息，可以用 vector 直接存。
对于每个虚树，最多只有 \(4n-1\) 个点，也就是最多只有 \(4n-2\) 条边，两棵树就是 \(8n-4\) 条边，还有相连的 \(n\) 条边，共 \(9n-4\) 条边，直接跑 kruskal，然后再以最左右两列建虚树即可。这里我建议直接跑两次 dfs 建虚树，因为关键点数和总点数非常接近，重建 LCA 的大常数和 dfs 大差不差，不如写 dfs 来的方便。
最终时间复杂度为 \(O(n(m+q)\log n)\)。
代码：
也都和别人同样思路的差不多了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
x=0;int f=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())ch=='-'&&(f=1);
for(;ch>='0'&&ch<='9';ch=getchar())x=(x*10)+(ch^48);
f&&(x=-x);
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){x<0&&(putchar('-'),x=-x);static int sta[35];int top=0;do{sta[++top]=x%10,x/=10;}while(x);while(top)putchar(sta[top--]^48);}
TP void writeln(const T x){write(x);puts("");}
TP void writesp(const T x){write(x);putchar(32);}
TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);}
using LL=long long;
constexpr int N=1e2+5;
constexpr int M=1e4+5;
int n,m;
int row[M][N],col[M][N];
struct edge
{
int x,y,c;
bool operator <(const edge &a)
{
return c<a.c;
}
};
struct MST
{
vector<edge>a;//该 MST 中可能被替换的边
int alen;
LL sum;//边权和
MST(){alen=0,sum=0;a.clear();}
MST(const int *c)
{
sum=0;
for(int i=1;i<n;i++)
a.push_back({i,i+1,c[i]});
sum=0;
alen=n;
}
LL query()
{
LL ans=0;
for(auto i:a)
ans+=i.c;
return ans+sum;//这棵树的总边权
}
}s[M],ps[M];
struct v_edge{int y,c,pre;}a[M];int alen,last[M];
void ins(edge &q)
{
a[++alen]=v_edge{q.y,q.c,last[q.x]};last[q.x]=alen;
a[++alen]=v_edge{q.x,q.c,last[q.y]};last[q.y]=alen;
}
int fa[M];
int findfa(int x)
{
return fa[x]=fa[x]==x?x:findfa(fa[x]);
}
int key[M];
LL ans;
vector<edge>g;
bool dfs1(int x,int fa)
{
int sum=0;
for(int k=last[x];k;k=a[k].pre)
{
int y=a[k].y;
if(y==fa)continue;
sum+=dfs1(y,x);
}
if(sum>=2)//最近公共祖先
key[x]=1;
sum+=key[x];
return sum;
}
void dfs2(int x,int fa,int val,int lst)
{
if(key[x])
{
if(lst)
g.push_back({key[x],lst,val});//两个关键点之间的边
lst=key[x];
ans-=val;
val=0;
}
for(int k=last[x];k;k=a[k].pre)
{
int y=a[k].y;
if(y==fa)continue;
dfs2(y,x,max(val,a[k].c),lst);
}
}
MST merge(const MST &a,const MST &b,const int *c)//右向左合并，是有顺序的！（我因此挂了一次）
{
int len=a.alen+b.alen;
g.clear();
for(edge i:a.a)//左树的边
g.push_back(i);
for(edge i:b.a)//右树的边
g.push_back({i.x+a.alen,i.y+a.alen,i.c});//因为已经重编号了，所以才可以这样方便的写
for(int i=1;i<=n;i++)//中间相连的边
g.push_back({a.alen-n+i,a.alen+i,c[i]});
sort(g.begin(),g.end());
alen=1;//重置链式前向星，不然会溢出
for(int i=1;i<=len;i++)
fa[i]=i,last[i]=0,key[i]=(i<=n||i>len-n);//最左和最右的点
ans=a.sum+b.sum;
for(edge i:g)
{
int tx=findfa(i.x),ty=findfa(i.y);
if(tx==ty)continue;
ans+=i.c,fa[tx]=ty;
ins(i);
}
dfs1(1,0);
g.clear();
int cnt=0;
for(int i=1;i<=len;i++)
if(key[i])
key[i]=++cnt;//重编号
dfs2(1,0,0,0);
MST res;
res.alen=cnt;
res.sum=ans;
res.a=g;
return res;
}
unsigned int SA,SB,SC;
int lim;
int getweight()
{
SA^=SA<<16;
SA^=SA>>5;
SA^=SA<<1;
unsigned int t=SA;
SA=SB;
SB=SC;
SC^=t^SA;
return SC%lim+1;
}
void gen()
{
read(n,m,SA,SB,SC,lim);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int w=getweight();
row[j][i]=w;
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
{
int w=getweight();
col[j][i]=w;
}
}
int main()
{
gen();
s[1]=MST(col[1]);
ps[m]=MST(col[m]);
for(int i=2;i<m;i++)
s[i]=merge(s[i-1],MST(col[i]),row[i-1]);
for(int i=m-1;i>1;i--)//这里逆着存后缀方便询问合并
ps[i]=merge(MST(col[i]),ps[i+1],row[i]);
int q;read(q);
while(q--)
{
int l,r;read(l,r);
writeln(merge(ps[r+1],s[l-1],row[m]).query());
}
return 0;
}