自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:55:46，当前版本为作者最后更新于2024-04-03 23:11:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先把每个点对应到各自的连通块，将每个连通块对应到一个区间。则问题转化为：

• 初始有若干个区间。你需要选择一些点 $x$，两个区间有边当且仅当他们都包含一个选了的点 $x$。
• 询问为：给出若干个区间，需要选择一些点使它们联通，最小化点集权值和。（注意其他区间也参与连边）

首先判掉不需要撒点的情况，然后对询问的区间做缩减操作：若两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$ 满足 $[l_1,r_1]\subseteq [l_2,r_2]$，则可以舍弃 $[l_2,r_2]$ 的限制，因为此时 $[l_1,r_1]$ 中至少撒一个点，一定会连通。

缩减完后，此时的区间没有包含关系，可以从左到右排序。

特判掉缩减完后只剩一个区间的情况，此时答案为 在区间内选一个权值最小的点。

考虑权值均为 $1$ 的情况。

选点的方案是从左到右贪心的过程。从最左的 $[l_1,r_1]$ 开始，假设当前连通的区间（所有）中，最右的右端点是 $R$，而下一个没被连通的区间（仅限询问区间）是 $[l_t,r_t]$，则：

若 $r_t>R$，则选择 $R$；否则选择 $r_t$。

对于选择 $r_t$ 的情况，相当于把 $t$ 这个区间消耗掉了；

对于 $r_t>R$ 选择 $R$ 的情况：会先选择 $R$，每次选的下一个点是当前连通的最右一个点，再将 $R$ 更新，直到某次 $r_t\le R$。这个过程可以用倍增跳来计算，预处理 $f_{i,j}$ 表示从 $i$ 开始选，选 $2^j$ 步跳到哪个点。

如果当前所有询问区间都被连通，则过程结束。

两个操作加起来只有 询问区间个数 次，于是复杂度为 $O(\sum T_k \log n)$。

接下来考虑权值为 $1,2$ 怎么做。

事实上只需要稍微改变一下状态。维护当前的答案 $ans$，设 $dp_{0/1}$ 表示当前跳的代价为 $ans-1$ 或 $ans$ 步，能达到的右端点最大值。

将倍增数组也改变状态，设 $f_{i,j,0/1}$ 从 $i$ 开始选，经过代价为 $2^k-1$ 或 $2^k$ 步，能达到的右端点最大值。

接下来同上述倍增过程一样做即可：

• 如果 $dp_{0/1}$ 两个位置都不在询问区间内，就要用倍增数组跳过一整个空挡。每次尝试 $ans\to ans+2^k$，由于倍增处理的是跳 $2^k-1,2^k$ 代价达到的最远 $R$，可以求出此时跳到的端点，判断端点是否已经超过下一个区间。
• 否则，将 $ans\to ans+1$，并计算 $ans+1$ 对应的位置，可以从 $dp_{0/1}$ 转移。

loj submission

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f

int n,m,Q,fa[maxn];

int P(int i,int j){
	return (i-1)*m+j;
}
int gf(int x){
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
void mg(int u,int v){
	fa[gf(u)]=gf(v);
}

int id[maxn];
pii to[maxn];
int k;
int nxt2[maxn],ban[maxn];
int wei[maxn],pre1[maxn];

int f[20][500005][2];

void get(vector<pii>&o){
	vector<pii>s;
	sort(ALL(o),[&](pii x,pii y){
		if(x.fi!=y.fi) return x.fi<y.fi;
		return x.se>y.se;
	});
	for(auto [l,r]:o){
		while(s.size() && s.back().se>=r) s.pop_back();
		s.pb(mkp(l,r));
	}
	o=s;
}

int solve()
{
	int q=read();
	vi o(q);
	For(i,0,q-1){
		int a=read(),b=read();
		o[i]=gf(P(a,b));
		o[i]=id[o[i]];
	}
	sort(ALL(o)),o.erase(unique(ALL(o)),o.end());
	if(o.size()==1) return 0;
	
	vector<pii>a;
	for(auto x:o) a.pb(to[x]);//cout<<"x: "<<x<<" "<<to[x].fi<<" "<<to[x].se<<"\n";
	get(a);
	
	int l=inf,r=-inf;
	for(auto [tl,tr]:a) l=min(l,tr),r=max(r,tl);
//	cout<<"l,r "<<l<<" "<<r<<"\n";
	if(ban[r]!=ban[l]) return -1;
	
//	for(auto [tl,tr]:a)cout<<"LR "<<tl<<" "<<tr<<"\n"; 
	
	auto in=[&](int x){
		if(x==-1)return 1;
		auto it=upper_bound(ALL(a),mkp(x,inf));
		if(it!=a.begin()){
			--it;
			if((it->fi)<=x && x<=(it->se)) return 1;
		}
		return 0;
	};
	
	auto getnxt=[&](int x){
		if(x==0) return l;
		int res=nxt2[x];
		auto it=upper_bound(ALL(a),mkp(x,inf));
		if(it!=a.end()) res=min(res,(it->se));
		return res;
	};
	
	int res=1;
	int dp[2]={0,pre1[l]};
//	cout<<"res1 "<<1<<" "<<dp[0]<<" "<<dp[1]<<"\n";
	
	while(dp[1]<r){
		if(!in(dp[0]) && !in(dp[1])){
			int lim=r;
			auto it=upper_bound(ALL(a),mkp(dp[1],inf));
			if(it!=a.end()) lim=min(lim,(it->fi));
			
			Rep(i,19,0){
				int tdp[2];
				tdp[0]=max(f[i][dp[0]][1],f[i][dp[1]][0]);
				int R=(dp[0]==0?l:nxt2[dp[0]]);
				tdp[1]=max(f[i][dp[1]][1],f[i][R][0]);
				tdp[1]=max(tdp[1],tdp[0]);
				if(tdp[1]<lim){
					dp[0]=tdp[0],dp[1]=tdp[1];
					res+=(1<<i);
				}
			}
			if(dp[1]>=r) break;
		}
		int nx=max(getnxt(dp[0]),pre1[getnxt(dp[1])]);
	//	cout<<"nxt "<<dp[1]<<" "<<getnxt(dp[1])<<" "<<pre1[2]<<" "<<pre1[getnxt(dp[1])]<<"\n";
		dp[0]=dp[1],dp[1]=nx;
		++res;
	//	cout<<"res "<<res<<" "<<dp[0]<<" "<<dp[1]<<"\n";
	}
	return res;
}

signed main()
{
	n=read(),m=read(),Q=read();
	For(i,0,n*m) fa[i]=i;
	For(i,1,n){
		string s;cin>>s;
		For(j,1,m-1) if(s[j-1]&1) mg(P(i,j),P(i,j+1));
	}
	For(i,1,n-1){
		string s;cin>>s;
		For(j,1,m) if(s[j-1]&1) mg(P(i,j),P(i+1,j));
	}
	For(i,0,n*m) to[i]=mkp(inf,-inf);
	For(i,1,n) For(j,1,m) {
		int x=gf(P(i,j));
		to[x].fi=min(to[x].fi,i);
		to[x].se=max(to[x].se,i);
	}
	For(i,1,n*m) 
		if(gf(i)==i) id[i]=++k,to[k]=to[i];
	
	For(i,1,k) nxt2[to[i].fi]=max(nxt2[to[i].fi],to[i].se);
	For(i,2,n) nxt2[i]=max(nxt2[i],nxt2[i-1]);
	For(i,1,n) ban[i]=ban[i-1]+(nxt2[i-1]<=i-1);
	
//	For(i,1,n)cout<<ban[i]<<" " ; cout<<" ban\n";
	
	For(i,1,n){
		wei[i]=read();
		if(wei[i]==1)pre1[i]=i;
		else pre1[i]=pre1[i-1];
	}
	
//	For(i,1,n) cout<<pre1[i]<<' '; cout<<"pre1\n";
//	For(i,1,n) cout<<nxt2[i]<<" "; cout<<"nxt2\n";
	
	For(i,1,n){
		f[0][i][0]=i;
		f[0][i][1]=max(i,pre1[nxt2[i]]);
	}
	
	For(j,1,19){
		auto F=[&](int i,int k){
			return f[j-1][i][k];
		};
		For(i,1,n){
			f[j][i][0]=max(F(F(i,1),0),F(F(i,0),1));
			f[j][i][1]=max(f[j][i][0],F(F(i,1),1));
			int x=F(i,0); x=max(x,nxt2[x]); x=F(x,0);
			f[j][i][1]=max(f[j][i][1],x);
		}
	}
	
	For(_,1,Q)printf("%d\n",solve());
	return 0;
}
/*
4 3 3
00
00
10
00
110
011
001
1 2 2 2
2
4 3
2 1
*/