「CF160E」Buses and People-线段树

Bertown 大街可以抽象为一条数轴。在数轴上有 $10^9$ 个巴士站。站点按照它们在数轴上的顺序从 $1$ 到 $10^9$ 的整数编号。这个城市有 $n$ 辆公共汽车。每天第 $i$ 个公共汽车从 $s_i$ 位置出发，到 $f_i$ 位置停止（ $s_i < f_i$ ），它在所有位于 $s_i$ 与 $f_i$ 的中间站点停靠并且仅在晚上返回。公共汽车在时间 $t_i$ 开始行驶，并且它也在时间 $t_i$ 完成行驶（行驶、停靠都是瞬间的）。所有公共汽车的开始时间 $t_i$ 都不同。公交车有无限的容量。

Bertown 有很多居民。今天第 $i$ 个人要从 $l_i$ 位置出发到 $r_i$ 位置结束（ $l_i < r_i$ ）；第 $i$ 个人在时间 $b_i$ 进入他的出发位置（ $l_i$ ）。一方面，每个人都希望尽快到达目的地，另一方面，他不想换乘公交车。

也就是：为第 $i$ 个人挑选的公交汽车 $j$ ，满足 $s_j \leq l_i$, $r_i \leq f_j$ 和 $b_i \leq t_j$ 的条件下，$t_j$ 最小。

你的任务是确定每个人今天是否可以到达目的地，如果可以，找到每个人将乘坐的公交车的号码，不可以则输出 $-1$ 。

题解

我只想到了一个线段树套set的 $O(n \log^2 n)$ 的做法，但 tutorial 给出了一个 $O((n+m) \log (n+m))$ 的优秀做法。

我们在这里从 $t$ 从小往大处理，按时间顺序加入每个人；加入车的时候只需要判断哪些人可以被这个车带走，然后这个车就是这些人的答案。

我们考虑使用一个线段树维护这个所有人。我们根据 $l[i]$ 从小到大建立这个树，每个位置放置一个人，维护区间的 $r[i]$ 最小值及出现位置。

当我们加入一个 $s_i,f_i$ 的车的时候，我们只需要在所有 $l[i]$ 大于 $s[i]$ 的部分中，找到一个 $r[i]$ 最小的人，把它删掉，然后持续到找不到这个人即可。最后还在树里面的都是无法乘车的人。

这个方法很好啊，比我树套树不知道高到哪里去了…

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii;

const int MAXN = 210000;

struct B{
  int l,r,t,id;
  bool operator < (const B &x)const{return t < x.t;}
}bus[MAXN],p[MAXN];
bool cmp(B &x,B &y){return x.l < y.l;}
struct Node{
  int minn,pos,id;
  bool operator < (const Node &x)const{return minn < x.minn;}
};

int n,m;
pii LL[MAXN];

namespace SegTree{
  Node t[MAXN<<2];
  #define lson (nown<<1)
  #define rson (nown<<1|1)
  #define mid ((l+r)/2)
  void build(int nown,int l,int r,int *id){
    if(l == r){
      t[nown] = (Node){inf,l,id[l]};
    }
    else{
      build(lson,l,mid,id),build(rson,mid+1,r,id);
      t[nown] = min(t[lson],t[rson]);
    }
  }
  void update(int nown,int l,int r,int pos,int v){//change v
    if(l == r)
      t[nown].minn = v;
    else{
      if(pos <= mid) update(lson,l,mid,pos,v);
      if(pos >= mid+1) update(rson,mid+1,r,pos,v);
      t[nown] = min(t[lson],t[rson]);
    }
  }
  Node query(int nown,int l,int r,int ql,int qr){
    if(ql <= l && r <= qr)
      return t[nown];
    else{
      Node ans = (Node){inf,0,0};
      if(ql <= mid) ans = min(ans,query(lson,l,mid,ql,qr));
      if(qr >= mid+1) ans = min(ans,query(rson,mid+1,r,ql,qr));
      return ans;
    }
  }
  #undef lson
  #undef rson
  #undef mid
}

void init(){
  scanf("%d %d",&n,&m);
  for(int i = 1;i<=n;i++){
    scanf("%d %d %d",&bus[i].l,&bus[i].r,&bus[i].t);
    bus[i].id = i;
  }
  for(int i = 1;i<=m;i++){
    scanf("%d %d %d",&p[i].l,&p[i].r,&p[i].t);
    LL[i] = make_pair(p[i].l,i);
    p[i].id = i;
  }
  sort(LL+1,LL+m+1);
  sort(p+1,p+m+1),sort(bus+1,bus+n+1);
}

int xx[MAXN];
int tmp[MAXN],pos[MAXN],ans[MAXN];

void build(){
  for(int i = 1;i<=m;i++) 
    tmp[i] = LL[i].second,xx[i] = LL[i].first,pos[LL[i].second] = i;
  SegTree::build(1,1,m,tmp);
}

void add_person(int now){
  SegTree::update(1,1,m,pos[p[now].id],p[now].r);
}
void add_bus(int now){
  int L = lower_bound(xx+1,xx+m+1,bus[now].l) - xx;
  if(L == m+1) return;
  while(true){
    Node t = SegTree::query(1,1,m,L,m);
    if(t.minn > bus[now].r) break;
    else{
      ans[t.id] = bus[now].id;
      SegTree::update(1,1,m,t.pos,inf);
    }
  }
}

void solve(){
  int nx = 1,ny = 1;
  while(true){
    if(nx == (n+1)) break;
    if((nx != n+1 && ny == m+1) || bus[nx].t < p[ny].t )
      add_bus(nx++);// 新加入人？新加入车？
    else
      add_person(ny++);
  }
  for(int i = 1;i<=m;i++) printf("%d ",ans[i] == 0?-1:ans[i]);
  printf("\n");
}

int main(){
  init();
  build();
  solve();
  return 0;
}

「CF160E」Buses and People-线段树

题解

代码

See Also

Comments