一类线段覆盖与倍增问题.

Description

解决环上的线段覆盖问题.

Solution

首先把环延长一倍.

将线段按右端点排序, 预处理每个线段能接上的到达最远的线段, 作为父亲, 建出一颗树.

查询时跳树到指定距离为止, 取深度差即为答案.

然后有很多细节, 比如这两个题一个要求线段之间相邻, 一个要求相接.

还有4444那题每个线段起步都要求一遍, 所以每条线段都要复制一遍.

贴一道题作为参考:

BZOJ4444:

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

using namespace std;

const int maxn = 4e+5 + 1000;

struct edge {
  int to, nxt;
}e[maxn << 1];
struct line {
  int l, r, id, ori;
  inline bool operator<(const line &rhs) const {
    return r < rhs.r;
  }
}ln[maxn];
int n, m, c[maxn], d[maxn], lnk[maxn], bgn;
int cpy[maxn << 1], cnt, f[21][maxn];
int far[maxn << 1], dep[maxn];
int spe[maxn];

template<typename T>
inline void rd(T &x) {
  x = 0; register int c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
}
void ged(int x) {
  //if (x >= 300000)printf("%d\n", x);
  if (!f[0][x]) dep[x] = 1;
  if (dep[x]) {
    //if (x >= 224000) printf("ret %d\n", x);
    return;
  }
  ged(f[0][x]);
  dep[x] = dep[f[0][x]] + 1;
}
inline int query(int x, int dst) {
  for (int i = 20; ~i; --i)
    if (f[i][x] && ln[f[i][x]].r < dst) x = f[i][x];
  return ln[x].r >= dst ? x : f[0][x];
}

int main() {
  // freopen("7.in", "r", stdin);
  //freopen("my.out", "w", stdout);
  rd(m); rd(n);
  int tot = m;
  for (int i = 1; i <= m; ++i) {
    rd(ln[i].l); rd(ln[i].r); ln[i].ori = ln[i].l + n;
    ln[i].id = i;
    if (ln[i].l < ln[i].r) {
      ln[++tot] = (line){ln[i].l + n, ln[i].r + n};
    } else {
      ln[i].r += n;
      ln[++tot] = (line){ln[i].l + n, 2 * n};
    }
    cpy[++cnt] = ln[i].l;
    cpy[++cnt] = ln[i].r;
    cpy[++cnt] = ln[tot].l;
    cpy[++cnt] = ln[tot].r;
  } 
  swap(m, tot);
  cpy[++cnt] = 1; cpy[++cnt] = n;
  sort(cpy + 1, cpy + 1 + cnt);
  cnt = unique(cpy + 1, cpy + 1 + cnt) - (cpy + 1);
  
  for (int i = 1; i <= m; ++i) {
    ln[i].l = lower_bound(cpy + 1, cpy + 1 + cnt, ln[i].l) - cpy;
    ln[i].r = lower_bound(cpy + 1, cpy + 1 + cnt, ln[i].r) - cpy;
  }
  sort(ln + 1, ln + 1 + m);
  for (int i = 1; i <= m; ++i)
    far[ln[i].l] = max(far[ln[i].l], i);
  /*for (int i = 1; i <= cnt; ++i)
    printf("%d %d\n", i, far[i]);*/
  int ptr = 0;
  function<bool(int, int)> func = [](int a, int b) -> bool{return ln[a] < ln[b];};
  function<int(int, int)> g = [](int id, int ptr) -> int{return ptr == id ? 0 : ptr;};
  for (int l = 1, i = 1; i <= m; ++i) {
    for (; l <= ln[i].r; ++l)
      ptr = max(ptr, far[l], func);
    f[0][i] = g(i, ptr);
    // printf("-%d %d\n", i, f[0][i]);
  }
  // puts("init");
  for (int i = 1; i <= 20; ++i)
    for (int j = 1; j <= m; ++j)
      f[i][j] = f[i - 1][f[i - 1][j]];
  // puts("mul");
  for (int i = 1; i <= m; ++i)
    ged(i);
  // puts("ged");
  // solve 1st problem
  int ans = 0x3f3f3f3f;
  for (int i = 1; i <= m; ++i) {
    int dst = lower_bound(cpy + 1, cpy + 1 + cnt, ln[i].ori) - cpy;
    int bas = query(i, dst); 
    // if (ln[i].id && ln[i].id >= 180000) printf("%d %d\n", i, bas);
    if (bas && ln[i].id) {
      spe[ln[i].id] = dep[i] - dep[bas] + 1;
      // if (ln[i].id >= 180000) printf("%d\n", spe[ln[i].id]);
      ans = min(ans, spe[i]);
    }
  } 
  for (int i = 1; i <= tot; ++i)
    printf("%d ", spe[i]);
  return 0;
}