「JOI 2024 Final」路网服务 2

Rainbow_qwq · 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
*/