[ABC128E] Roadwork 题解

· · 题解

这里提供一种比较奇怪的数据结构做法。

本题需要利用优先队列与线段树。

先考虑如果一个点的施工永远不会结束应该怎么做：假设出发时间为 D，显然可以二分出最近的点 X_j，这个点满足所有离它近的点 X_i 都在人走过去之后才开始施工（条件为 D+X_i<S_i，为方便处理将它变为 D<S_i-X_i），并且人会卡在 X_j 上（即人到达 X_j 的时候它已经开始施工了）。这个可以用线段树维护 S_i-X_i 的区间最小值。

考虑如果施工时间会结束应该怎么做。因为询问的出发时间是递增的，所以如果目前问到的 D 存在一段施工结束时间 T_i\le X 的，可以删除这一段施工并且以后都用不到，如果该点的下一段施工满足 T_i>X 就更新线段树，否则继续删除施工时间继续往下找（即同一个点可能存在不止一段 T_i\le X 的施工），最终如果这个点都没有施工了就将其值设为 \inf。删除哪些段可以用优先队列维护。

线段树可以借助 AtCoder Library，有自带二分函数 max_right<>()。

放代码（GNU C++ 17, with AtCoder Library）：

// AtCoder Segtree + Priority Queue
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
int op(int a,int b){return min(a,b);}
int e(){return INT_MAX;}
int d; bool f(int x){return x>d;}
int main(){
  ios::sync_with_stdio(false);
  int n,m,c=-1; cin>>n>>m;
  vector<tuple<int,int,int> > a(n);
  for(auto &[x,l,r]:a)cin>>l>>r>>x,l=max(l-x,0),r=max(r-x,0);
  sort(a.begin(),a.end());
  map<int,int> w;
  map<int,queue<pii> > v;
  vector<int> p;
  for(auto [x,l,r]:a){
    if(!w.count(x))w[x]=++c,p.emplace_back(x);
    v[c].emplace(l,r);
  }
  p.emplace_back(-1);
  priority_queue<pii,vector<pii>,greater<> > q;
  atcoder::segtree<int,op,e> t(c+1);
  for(auto [x,l,r]:a)
    if(int y=w[x];t.get(y)==INT_MAX)t.set(y,l),q.emplace(r,y);
  // 以上为预处理
  while(m--&&cin>>d){
    while(!q.empty()&&q.top().first<=d){
      int x=q.top().second; q.pop();
      while(!v[x].empty()&&v[x].front().second<=d)v[x].pop();
      if(v[x].empty())t.set(x,INT_MAX);
      else t.set(x,v[x].front().first),q.emplace(v[x].front().second,x);
    } // 删除工作段
    cout<<p[t.max_right<f>(0)]<<'\n'; // 二分找答案
  }
  return 0;
}