Atcoder abc254 G(倍增)

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘

G(倍增)

G

题目

https://atcoder.jp/contests/abc254/tasks_print

n个楼, 每个楼高都是1..1e9

有m个电梯, 每个电梯在一个楼里,负责[li,ri] 之间

可以允许这个楼里, [li,ri] 范围中的移动

跨楼同楼层移动代价1

同楼电梯内移动,代价 高度差

q个询问, ai楼bi层 到 ci楼di层最小代价, 或它们不可达

范围

n 2e5

m 2e5

q 2e5

6s

1024mb

题解

我的思路

显然 同楼层答案是1或0

不同楼层,只会单调移动,不会先上再下这种, 答案 = 距离+跨楼数, 需要最小化跨楼数

而每次移动贪心距离, 这样模拟可做, 但是复杂度无法接受

显然同楼的重叠电梯可以合并

官方

显然上下还满足对称性, 那么只考虑从下向上

合并同楼重叠电梯(这样做了以后剩下的线段就不用考虑属于哪个楼了? 因为是一旦重叠肯定不重楼

如果 ai楼内bi移动到最高位置, ci 楼内 di 移动到最低位置, 合法提前输出

dp[i][j] 当前建筑第i层,用j个电梯后最高能到达的楼层

考虑 离散+倍增

代码

我写的按右断点跳右端点的map不知道为什么WA了除了测试点, 调了七八个小时,atcoder还没数据, 放弃了

下面是一个别人的代码,我改了部分格式,靠清理了一些线段,保持左右端点都严格单调递增, 然后用线段跳线段来做的, 我觉得完全一样啊, 吐了, 搞不动了,心态炸了

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
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
#define pb push_back

int read(){int r;scanf("%d",&r);return r;} // read

vector<array<int,2> > ilr[200010];
vector<array<int, 2>> segs;
vector<vector<int>> jump;

int N;
int lg = 20;

int n, m, q;

int query(){
  int i0, f0, i1, f1;
  i0 = read() - 1;
  f0 = read();
  i1 = read() - 1;
  f1 = read();

  if(f0 == f1) return i0 != i1;

  if (f0 > f1) {
    swap(i0, i1);
    swap(f0, f1);
  }

  int ans = f1 - f0;
  auto it =
    lower_bound(ilr[i0].begin(), ilr[i0].end(), array<int, 2>{f0 + 1, -1});
  if (it != ilr[i0].begin()) f0 = max(f0,(*--it)[1]);

  it = lower_bound(ilr[i1].begin(), ilr[i1].end(), array<int, 2>{f1 + 1, -1});
  if (it != ilr[i1].begin()) {
    it--;
    if (f1 <= (*it)[1]) {
      f1 = (*it)[0];
    }
  }

  if (f0 >= f1) return ans + (i0 != i1);
  // 跳到一个右端点 保证f0 是右端点
  ans++;
  int idx = lower_bound(segs.begin(), segs.end(), array<int, 2>{f0 + 1, -1}) - segs.begin();
  // 未被覆盖到
  if (!idx) return -1;
  idx--;
  if (f0 > segs[idx][1]) return -1;
  if (segs[idx][1] >= f1) return ans + 1;
  if (segs[jump[idx][lg]][1] < f1) return -1;
  per(k,0,lg+1){
    if (segs[jump[idx][k]][1] >= f1) continue;
    idx = jump[idx][k];
    ans += 1 << k;
  }
  idx = jump[idx][0];
  return ans + 2;
}

int main() {
  n = read();
  m = read();
  q = read();
  rep(i,0,m){
    int a, b, c;
    a = read() - 1;
    b = read();
    c = read();
    ilr[a].push_back({b, c});
  }
  // 每组内部 排序 与 合并
  rep(i,0,n){
    sort(ilr[i].begin(), ilr[i].end());
    vector<array<int, 2>> temp;
    for (auto [l, r] : ilr[i]) {
      if (!temp.empty() && l <= temp.back()[1]) {
        temp.back()[1] = max(temp.back()[1], r);
      } else {
        temp.push_back({l, r});
      }
    }
    ilr[i] = temp;
    for (auto s : temp) segs.push_back(s);
  }

  sort(segs.begin(), segs.end());

  vector<array<int, 2>> temp;
  for (auto [l, r] : segs) {
    if (!temp.empty() && r <= temp.back()[1]) { //
      continue;
    }
    if (!temp.empty() && l == temp.back()[0]) {
      temp.pop_back();
    }
    temp.push_back({l, r});
  }
  segs = temp;

  N = segs.size();
  jump = vector<vector<int>>(N, vector<int>(lg + 1));

  // jump[段id][pwr] = 段id
  for (int i = 0, j = 0; i < N; i++) {
    while (j + 1 < N && segs[j + 1][0] <= segs[i][1]) {
      j++;
    }
    jump[i][0] = j;
  }
  rep(j,0,lg){
    rep(i,0,N){
      jump[i][j + 1] = jump[jump[i][j]][j];
    }
  }


  while(q--) printf("%d\n", query());
  return 0;
}

我的代码 不知道WA在哪里了

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n,m,q;

vector<pair<int,int> > ilr[200010]; // 每个楼

vector<pair<int,int> > segs; // 所有楼
vector<int> maxr = {0}; // 前缀 最大r
map<int,vector<int>> jump = {}; // jump[结束位置][2**i次跳跃] = 最高位置

const int lg = 20;

int query(){
  int i0 = read();
  int f0 = read();
  int i1 = read();
  int f1 = read();
  // 同楼层
  if(f0 == f1) return i0 != i1;

  // 从低到高 f0 < f1
  if(f0 > f1){
    swap(i0,i1);
    swap(f0,f1);
  }
  int ans = f1-f0;

  // 注意不在区间的情况不会跳
  int itr0 = lower_bound(ilr[i0].begin(),ilr[i0].end(),make_pair(f0+1,-1)) - ilr[i0].begin();
  if(itr0 > 0) f0 = max(f0, ilr[i0][itr0-1].second);

  int itr1 = lower_bound(ilr[i1].begin(),ilr[i1].end(),make_pair(f1+1,-1)) - ilr[i1].begin();
  if(itr1 > 0 && ilr[i1][itr1-1].second >= f1) f1 = ilr[i1][itr1-1].first;

  if(f1 <= f0) return ans + (i0 != i1);

  // next0 可能不是某个右端点, 不可能一次跳到, 否则 perv1 <= next0, 所以直接贪心去最大可达右端点
  // 跳一次 保证f0 是右端点
  int idx = lower_bound(segs.begin(),segs.end(),make_pair(f0+1,-1)) - segs.begin();
  if(idx == 0 || maxr[idx] < f0) return -1; // 未被覆盖到
  f0 = maxr[idx]; // 当不可达时可能是比它小的右端点, 但是不影响结果逻辑
  ans ++;
  if(f1 <= f0) return ans + 1;

  // ? 需要吗 TODO
  // if(!h.count(f0)) return -1;

  if(jump[f0][lg] < f1) return -1;

  per(pwr,0,lg+1){
    if(jump[f0][pwr] >= f1) continue;
    f0 = jump[f0][pwr];
    ans += (1<<(pwr));
  }
  assert(f0 < f1 && jump[f0][0] >= f1);
  // printf("%d\n",ans+1 +1); // 分别是跳到比f1 大的和跳到恰好f1
  return ans + 2; // 分别是跳到比f1 大的和跳到恰好f1
}

int main(){
  n = read();
  m = read();
  q = read();
  rep(i,0,m) {
    // 注意g++ 函数处理顺序问题
    // ilr[read()].pb(make_pair(read(),read()));
    int pos = read();
    int l = read();
    int r = read();
    ilr[pos].pb({l,r});
  }
  // 合并同楼 重叠
  rep(i,1,n+1){
    sort(ilr[i].begin(),ilr[i].end());
    vector<pair<int,int> > tmp = {}; // 合并辅助
    for(auto [l,r]: ilr[i]){
      if(tmp.size() == 0 || l > tmp.back().second){ // 不连续 [l0,r0] .. [l1..r1]
        tmp.pb({l,r});
      }else{
        tmp.back().second = r;
      }
    }
    ilr[i] = tmp;
    for(auto o:tmp) segs.pb(o);
  }
  sort(segs.begin(),segs.end()); // 所有楼的
  for(auto item:segs) maxr.pb(max(maxr.back(), item.second));
  // 倍增
  for(auto item:segs){
    auto r = item.second;
    if(jump.count(r)) continue;
    jump[r] = vector<int>(lg+1,r);
    // [...r] [r+1...
    int idx = lower_bound(segs.begin(),segs.end(),make_pair(r+1,-1)) - segs.begin();
    jump[r][0] = maxr[idx]; // 初始化跳2^0 = 1次
  }
  rep(pwr,1,lg+1){
    for(auto item:segs){ // 会重复计算,不影响
      auto r = item.second;
      jump[r][pwr] = jump[jump[r][pwr-1]][pwr-1];
    }
  }

  while(q--) printf("%d\n", query());
  return 0;
}

总结

G

倍增, 编码速度也是问题, 写几个小时还在wa,哎

参考

官方题解 https://atcoder.jp/contests/abc254/editorial