Description

给定一个 $n\times m$ 的网格图。从 $(i,j)$ 向右，向下边的权值分别为 $a_{i,j},b_{i,j}$，特别地，认为第 $m$ 列和第 $1$ 列相邻。

$q$ 次查询 $(l_j,r_j)$，求出原图删去第 $[l_j,r_j]$ 列后的 MST 边权和。

Limitations

$1\le n\le 100$

$1\le m,q\le 10^4$

$1\le a_{i,j},b_{i,j}\le 10^9$

$1<l_j\le r_j<m$

$3\text{s},500\text{MB}$

Solution

比较新颖的题，视 $m,q$ 同阶。考虑求出前后缀的 MST 信息，查询时合并，但是维护整棵 MST 显然会爆掉。

发现 $n$ 很小，考虑维护 $O(n)$ 大小的信息。显然合并 MST 时只有两端的节点有用，于是只维护这些节点间的关键边（对于其他边只记录权值和），合并时取出两边的关键边跑 Kruskal，并求出新 MST 的关键边即可（需要给关键点重编号）。

由于要对边排序所以复杂度为 $O(nm\log n)$。

::::info[code]

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

struct dsu {
	vector<int> f;
	dsu() {}
	dsu(int n) : f(n) {
		iota(f.begin(), f.end(), 0);
	}
	
	int find(int x) {
		while (x != f[x]) x = f[x] = f[f[x]];
		return x;
	}
	
	bool unite(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return false;
		f[v] = u; return true;
	}
};

struct Edge {
	int u, v; i64 cost;
	Edge() {}
	Edge(int u, int v, i64 cost) : u(u), v(v), cost(cost) {}
	bool operator<(const Edge& b) const { return cost < b.cost; }
};

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	static int N, M, lim;
	unsigned sa, sb, sc;
	cin >> N >> M >> sa >> sb >> sc >> lim;
	
	auto rand = [&]() {
		sa ^= sa << 16;
		sa ^= sa >> 5;
		sa ^= sa << 1;
		unsigned t = sa;
		sa = sb;
		sb = sc;
		sc ^= t ^ sa;
		return sc % lim + 1;
	};
	
	vector A(N, vector<int>(M));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) A[i][j] = rand();
	
	vector B(N, vector<int>(M));
	for (int i = 0; i < N - 1; i++)
		for (int j = 0; j < M; j++) B[i][j] = rand();
	
	struct Group {
		int n;
		i64 cost;
		vector<Edge> edges;
		int left(int x) const { return x; }
		int right(int x) const { return (n == N) ? x : (N + x); }
	};
	
	auto column = [&](int y) {
		Group f;
		f.n = N, f.cost = 0;
		for (int x = 0; x < N - 1; x++) f.edges.emplace_back(x, x + 1, B[x][y]);
		return f;
	};
	
	auto merge = [&](const Group &f, int y, const Group &g) {
		Group h;
		h.n = N + N;
		h.cost = f.cost + g.cost;
		
		vector<Edge> edges;
		for (auto e : f.edges) edges.push_back(e);
		for (auto e : g.edges) edges.emplace_back(f.n + e.u, f.n + e.v, e.cost);
		for (int x = 0; x < N; x++) edges.emplace_back(f.right(x), f.n + g.left(x), A[x][y]);
		sort(edges.begin(), edges.end());
		
		dsu uf0(f.n + g.n), uf1(f.n + g.n);
		for (int x = 0; x < N; x++) uf0.unite(f.left(0), f.left(x));
		for (int x = 0; x < N; x++) uf0.unite(f.left(0), f.n + g.right(x));
		
		for (auto e : edges) {
			if (uf0.unite(e.u, e.v)) {
				h.cost += e.cost;
				uf1.unite(e.u, e.v);
			}
		}
		
		vector<int> id(f.n + g.n, -1);
		for (int x = 0; x < N; x++) id[uf1.find(f.left(x))] = x;
		for (int x = 0; x < N; x++) id[uf1.find(f.n + g.right(x))] = N + x;
		
		dsu uf2(N + N);
		for (auto e : edges) {
			int u = id[uf1.find(e.u)], v = id[uf1.find(e.v)];
			if (uf2.unite(u, v)) h.edges.emplace_back(u, v, e.cost);
		}
		return h;
	};
	
	vector<Group> pre(M), suf(M);
	pre[0] = column(0);
	for (int y = 0; y < M - 1; y++) pre[y + 1] = merge(pre[y], y, column(y + 1));
	
	suf[M - 1] = column(M - 1);
	for (int y = M - 2; y >= 0; y--) suf[y] = merge(column(y), y, suf[y + 1]);
	
	auto query = [&](int l, int r) {
		Group res = merge(suf[r + 1], M - 1, pre[l - 1]);
		i64 ans = res.cost;
		for (auto e : res.edges) ans += e.cost;
		return ans;
	};
	
	int Q; cin >> Q;
	for (int i = 0, l, r; i < Q; i++) {
		cin >> l >> r, l--, r--;
		cout << query(l, r) << '\n';
	}
	
	return 0;
}
``
::::

#include <bits/stdc++.h>
using namespace std;
unsigned int SA, SB, SC;
int lim;
int n, m;
int ex[10010][105], ey[10010][105];
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()
{
    scanf("%d%d%u%u%u%d", &n, &m, &SA, &SB, &SC, &lim);
    int i, j, w;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            w = getweight();
            ex[j][i] = w;
        }

    for (i = 1; i < n; i++)
        for (j = 1; j <= m; j++)
        {
            w = getweight();
            ey[j][i] = w;
        }
}
typedef long long ll;
struct edge
{
    int u, v, w;
    edge(int a, int b, int c) : u(a), v(b), w(c) {}
    bool operator < (const edge B) const {
        return w < B.w;
    }
};
int id(int x, int y)
{
    return (x - 1) * n + y;
}
int key[1000100], f[1000100];
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
ll kruskal(vector<edge> &a, vector<edge> &b)
{
    ll ans = 0;
    sort(a.begin(), a.end());
    b.clear();

    for (int i = 0; i < a.size(); ++i)
    {
        int fu = find(a[i].u), fv = find(a[i].v);

        if (fu == fv)
            ans += a[i].w;
        else
        {
            if (key[fu] && key[fv])
                f[fu] = fv, b.push_back(edge(fu, fv, a[i].w));
            else if (key[fu])
                f[fv] = fu;
            else
                f[fu] = fv;
        }
    }

    return ans;
}
vector<edge> pre[10010], suf[10010];
ll pres[10010], sufs[10010];
void upt(int x, int op)
{
    f[x] = x;
    key[x] = op;
}
vector<edge> a, b;
void getPre()
{
    a.clear();

    for (int i = 1; i <= n * m; ++i)f[i] = i, key[i] = 0;

    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            upt(id(i, j), 1);
            upt(id(1, j), 1);

            if (i > 2)
                upt(id(i - 1, j), 0);
        }

        for (int j = 1; j <= n; ++j)
        {
            if (i != 1)
            {
                a.push_back(edge(id(i, j), id(i - 1, j), ex[i - 1][j]));
                pres[i] += ex[i - 1][j];
            }

            if (j != n)
            {
                a.push_back(edge(id(i, j), id(i, j + 1), ey[i][j]));
                pres[i] += ey[i][j];
            }
        }

        ll del = kruskal(a, b);
        pres[i] += pres[i - 1] - del;
        pre[i] = b;
        a = b;
    }
}
void getSuf()
{
    a.clear();

    for (int i = 1; i <= n * m; ++i)f[i] = i, key[i] = 0;

    for (int i = m; i >= 1; --i)
    {
        for (int j = 1; j <= n; ++j)
        {
            upt(id(i, j), 1);
            upt(id(m, j), 1);

            if (i < m - 1)
                upt(id(i + 1, j), 0);
        }

        for (int j = 1; j <= n; ++j)
        {
            if (i != m)
            {
                a.push_back(edge(id(i, j), id(i + 1, j), ex[i][j]));
                sufs[i] += ex[i][j];
            }

            if (j != n)
            {
                a.push_back(edge(id(i, j), id(i, j + 1), ey[i][j]));
                sufs[i] += ey[i][j];
            }
        }

        ll del = kruskal(a, b);
        sufs[i] += sufs[i + 1] - del;
        suf[i] = b;
        a = b;
    }
}
int l, r, q;
int main()
{
    gen();
    getPre();
    getSuf();
    scanf("%d", &q);

    while (q--)
    {
        a.clear();
        scanf("%d %d", &l, &r);
        ll ans = 0;

        for (int i = 1; i <= n; ++i)
        {
            a.push_back(edge(id(1, i), id(m, i), ex[m][i]));
            upt(id(1, i), 0);
            upt(id(m, i), 0);
            upt(id(l - 1, i), 0);
            upt(id(r + 1, i), 0);
            ans += ex[m][i];
        }

        for (int i = 0; i < pre[l - 1].size(); ++i)a.push_back(pre[l - 1][i]);
        for (int i = 0; i < suf[r + 1].size(); ++i)a.push_back(suf[r + 1][i]);

        ll del = kruskal(a, b);
        ans += pres[l - 1] + sufs[r + 1] - del;
        printf("%lld\n", ans);
    }

    return 0;
}

ccf:

#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)const{return c<a.c;}
};
struct MST
{
    vector<edge>a;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]={q.y,q.c,last[q.x]};last[q.y]=alen;a[++alen]={q.x,q.c,last[q.y]};last[q.x]=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);}key[x]|=(sum>=2);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,key[i]=(i<=n||i>len-n),last[i]=0;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;
}