joisc 2023 护照

这题题意好难理解。

题目链接

P9331 [JOISC 2023 Day1] Passport

题意描述

有 \(n\) 个点，每个点连边连向编号在 \([L_i,R_i]\) 间的点，有 \(Q\) 组询问，每次从 \(x\) 号点出发，求出到 \(1\) 号点和到 \(n\) 号点的两条路径经过点的并集的最小值。

• \(n,Q\leq 2\cdot 10^5\)

解法

最优的的路径一定是先从 \(x\) 走到一个点 \(p\)，再从 \(p\) 分出两条路径分别走到 \(1\) 和 \(n\) 号点，这是容易观察到的。

这样答案就可以表示为 \(\min\limits_{i=1}^n \{dist_{x,i}+dist_{i,1}+dist_{i,n}\}\)。

可以先在反图上对每个点 \(i\) 求出 \(dist_{i,1}\) 和 \(dist_{i,n}\)，使用线段树优化出边可以做到 \(O(n\log n)\)。每次询问用 set 维护没有入队的点求出 \(x\) 的单源最短路，可以单次 \(O(n\log n)\) 求原图最短路。这样就有了 \(O(qn\log n)\) 的做法。

我们发现，可以对反图建立一个超级源点，对每个点连接边权为 \(dist_{i,1}+dist_{i,n}\) 的边，然后跑超级源点的单源最短路，就可以求出每个点处的答案。使用线段树优化，做到 \(O(n\log^2 n)\)。

代码

#include<bits/stdc++.h>

using namespace std;
const int inf=10000000,N=200010;

int n,q;
vector<int> L,R;
vector<int> node[N<<2];

void add(int u,int l,int r,int L,int R,int v){
  if(L<=l&&r<=R){
    node[u].emplace_back(v);
    return;
  }
  int mid=(l+r)>>1;
  if(L<=mid) add(u<<1,l,mid,L,R,v);
  if(mid<R) add(u<<1|1,mid+1,r,L,R,v);
}

vector<int> stk;
void get(int u,int l,int r,int pos){
  stk.insert(stk.end(),node[u].begin(),node[u].end());
  node[u].clear();
  if(l==r) return ;
  int mid=(l+r)>>1;
  if(pos<=mid) get(u<<1,l,mid,pos);
  else get(u<<1|1,mid+1,r,pos);
}

int main(){
  //freopen("in.in","r",stdin);
  cin.tie(0),cout.tie(0)->sync_with_stdio(false);

  cin>>n;
  L=R=vector<int>(n+1);
  for(int i=1; i<=n; i++){
    cin>>L[i]>>R[i];
  }

  vector<int> d1(n+1),d2(n+1);
  auto get_dist=[&](int sr,vector<int> &dis)->void{
    set<int> st;
    for(int i=1; i<=n; i++) st.insert(i);
    dis=vector<int>(n+1,inf);
    dis[sr]=0;
    deque<int> Q;
    Q.push_back(sr);
    st.erase(sr);
    while(Q.size()){
      int u=Q.front();
      Q.pop_front();

      auto pnt=st.lower_bound(L[u]);
      while(pnt!=st.end()&&(*pnt)<=R[u]){
        dis[*pnt]=dis[u]+1;
        Q.push_back(*pnt);
        auto tmp=next(pnt);
        st.erase(pnt);
        pnt=tmp;
      }
    }
  }; // 求原图的 SSSP，在可通过所有数据的解法中未使用

  d1=d2=vector<int>(n+1,inf);
  for(int i=2; i<=n; i++){
    add(1,1,n,L[i],R[i],i);
  }
  deque<int> Q;
  d1[1]=0;
  Q.push_back(1);
  while(Q.size()){
    int u=Q.front();
    Q.pop_front();

    stk.clear();
    get(1,1,n,u);
    for(auto p:stk){
      if(d1[p]!=inf) continue;
      Q.push_back(p);
      d1[p]=d1[u]+1;
    }
  }

  for(int i=1; i<=n*4; i++) node[i].clear();
  for(int i=1; i<n; i++){
    add(1,1,n,L[i],R[i],i);
  }
  d2[n]=0;
  Q.push_back(n);
  while(Q.size()){
    int u=Q.front();
    Q.pop_front();

    stk.clear();
    get(1,1,n,u);
    for(auto p:stk){
      if(d2[p]!=inf) continue;
      Q.push_back(p);
      d2[p]=d2[u]+1;
    }
  }

  for(int i=1; i<=n*4; i++) node[i].clear();
	
  vector<int> dis(n+1,inf);
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
  for(int i=2; i<n; i++){
  	dis[i]=d1[i]+d2[i]-1;
	pq.push(make_pair(d1[i]+d2[i]-1,i));
  }
  dis[n]=d1[n];
  dis[1]=d2[1];
  pq.push(make_pair(d1[n],n));
  pq.push(make_pair(d2[1],1));
  for(int i=1; i<=n; i++){
    add(1,1,n,L[i],R[i],i);
  }
	
  while(pq.size()){
	auto T=pq.top(); pq.pop();
	
	int u=T.second;
	stk.clear();
	get(1,1,n,u);
	for(auto p:stk){
	  if(dis[p]>dis[u]+1){
		dis[p]=dis[u]+1;
		pq.push(make_pair(dis[p],p));
      }
	}
  }
  cin>>q;
	
  while(q--){
	int x;
	cin>>x;
	if(dis[x]>n) dis[x]=-1;
	cout<<dis[x]<<'\n';
  }

  return 0;
}