QOJ #10042. Scheduling 题解

Description

给定 nn 个二元组 (li,ri)(l_i,r_i)，请你构造一个长度为 nn 的序列 aa，满足：

  • ∀1≤i≤n\forall 1\le i\le n，li≤ai≤ril_i\le a_i\le r_i；
  • ∀1≤i<j≤n\forall 1\le i<j\le n，∣ai−aj∣≥2|a_i-a_j|\ge2。

有 TT 组数据。

1≤T≤100,1≤∑n≤2×105,1≤li≤ri≤1061\le T\le 100,1\le \sum n\le 2\times 10^5,1\le l_i\le r_i\le 10^6。

Solution

首先如果只要求互不相同就是个经典的贪心，对区间按照 rr 排序，每次选择 ≥li\geq l_i 的最小的数选。

但是这里显然不能这么做。考虑通过构造候选集合，来转化成上面的那个贪心。

即构造一个序列 b1,b2,…,bmb_1,b_2,\ldots,b_m，满足 ∀1≤i<j≤m,∣bi−bj∣≥2\forall 1\leq i<j\leq m,|b_i-b_j|\geq 2 且满足最终的答案都在这里面选。

注意到如果给定 bb 序列，这就是个单点匹配区间的问题，可以用 Hall 定理判断有无解。

所以考虑 Hall 定理。

设 F(l,r)F(l,r) 表示包含于 [l,r][l,r] 的询问区间数，G(l,r)=r−l+1−2⋅F(l,r)G(l,r)=r-l+1-2\cdot F(l,r)，可以用线段树+扫描线维护 G(l,r)G(l,r) 的值。

那么如果存在 l,rl,r，使得 G(l,r)≤−2G(l,r)\leq -2，那么无论怎么填都不能满足这个区间的限制，也就是无解。

如果 G(l,r)=−1G(l,r)=-1，那么这个区间一定是填形如 10101011010101 这样一个 11 一个 00 交错的形式。

其余的先不管。

把所有满足 G(l,r)=−1G(l,r)=-1 的区间拿出来后，已经可以确定一部分位置的答案了，把这些已知的为 11 的位置 c1,c2,…,ckc_1,c_2,\ldots,c_k 拿出来后容易发现不同区间之间的填法基本上是独立的，考虑从前往后对于 [ci+1,ci+1−1][c_i+1,c_{i+1}-1] 分别做。

如果 (ci+1−ci) mod 2=0(c_{i+1}-c_i)\bmod 2=0，那么这个区间一定填的是 010101…010010101\ldots 010，其余的一定不优。

如果 (ci+1−ci) mod 2=1(c_{i+1}-c_i)\bmod 2=1，注意到现在不能像上面那样去完全交错填了，即一定存在一个 gg，满足 gg 和 g+1g+1 都是 00，可以发现 [ci,g−1][c_i,g-1] 和 [g+2,ci+1][g+2,c_{i+1}] 都交错着填一定更优。

由于 gg 越小对于后面的区间一定更优，所以只需要对于当前区间找到最小的能够满足所有 r≤ci+1r\leq c_{i+1} 的区间的限制的 gg 即可。

设 H(l,r)H(l,r) 表示 [l,r]没有确定答案的点数+2×([l,r]中确定的1的个数−包含于[l,r]的区间数)[l,r] 没有确定答案的点数+2\times \left([l,r] 中确定的 1 的个数-包含于 [l,r] 的区间数\right)，容易发现所有没有确定的点一定都在 (ci,ci+1)(c_i,c_{i+1}) 内。

考虑从前往后扫右端点 rr，找到满足 H(l,r)H(l,r) 最小的最小的 ll。

  • 如果 H(l,r)<0H(l,r)<0，显然 l≤cil\leq c_i，否则 ll 一定会被加到 cc 数组里。由于 ci+1c_i+1 一定填 00，所以无论如何也不能满足 [l,r][l,r] 的限制。

  • 如果 H(l,r)=0H(l,r)=0，则 gg 和 g+1g+1 出现在 [l,r][l,r] 里会让 H(l,r)H(l,r) 减为负数，不满足条件，给 [l,r][l,r] 打上标记表示 gg 不能出现在里面。

  • 如果 H(l,r)>0H(l,r)>0，则 gg 在哪里 [l,r][l,r] 都能满足条件，不管它。

最后 (ci,ci+1)(c_i,c_{i+1}) 里找最小的与 ci+1c_{i+1} 奇偶性相同且没被打上标记的位置就是 gg，然后更新线段树。

注意多组数据 ∑ri\sum r_i 是没有限制的，所以需要离散化。具体的做法是按照 ll 排序，然后每次找到 ≥li\geq l_i 的 33 没选的位置加进去，最后对 l,rl,r 分别二分找到对应取值，再做上面的东西。

时间复杂度：O(nlog⁡n)O(n\log n)。

Code

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <bits/stdc++.h>

// #define int int64_t

using pii = std::pair<int, int>;

const int kMaxN = 6e5 + 5;

int n, m, cnt;
int a[kMaxN], res[kMaxN], l[kMaxN], r[kMaxN], unq[kMaxN];
std::vector<int> vv[kMaxN];

struct SGT {
  pii mi[kMaxN * 4];
  int tag[kMaxN * 4];
  void pushup(int x) {
    mi[x] = std::min(mi[x << 1], mi[x << 1 | 1]);
  }
  void addtag(int x, int v) {
    mi[x].first += v, tag[x] += v;
  }
  void pushdown(int x) {
    if (tag[x]) {
      addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
      tag[x] = 0;
    }
  }
  void build(int x, int l, int r) {
    tag[x] = 0;
    if (l == r) return void(mi[x] = {0, l});
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void update(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }
  pii query(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {1e9, 0};
    else if (l >= ql && r <= qr) return mi[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    return std::min(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));
  }
} sgt;

void discrete() {
  std::vector<int> vec;
  for (int i = 1; i <= n; ++i) vec.emplace_back(l[i]);
  std::sort(vec.begin(), vec.end());
  int p = 0;
  m = 0;
  for (auto x : vec) {
    for (int i = 1; i <= 3; ++i) {
      unq[++m] = p = std::max(p + 1, x);
    }
  }
  for (int i = 1; i <= m; ++i) std::vector<int>().swap(vv[i]);
  for (int i = 1; i <= n; ++i) {
    l[i] = std::lower_bound(unq + 1, unq + 1 + m, l[i]) - unq;
    r[i] = std::lower_bound(unq + 1, unq + 1 + m, r[i]) - unq - 1;
    vv[r[i]].emplace_back(l[i]);
  }
}

bool getarr() {
  static int diff[kMaxN][2];
  cnt = 0, sgt.build(1, 1, m);
  for (int i = 0; i <= m; ++i) diff[i][0] = diff[i][1] = 0;
  for (int i = 1; i <= m; ++i) {
    sgt.update(1, 1, m, 1, i, 1);
    for (auto x : vv[i]) sgt.update(1, 1, m, 1, x, -2);
    auto p = sgt.query(1, 1, m, 1, i);
    if (p.first < -1) return 0;
    if (p.first == -1) {
      int j = p.second;
      ++diff[j][1], --diff[i + 2][1];
      ++diff[j + 1][0], --diff[i + 1][0];
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (i >= 2) diff[i][0] += diff[i - 2][0], diff[i][1] += diff[i - 2][1];
    if (diff[i][0] && diff[i][1]) return 0;
    if (diff[i][1]) a[++cnt] = i;
  }
  int lst = cnt;
  sgt.build(1, 1, m);
  if (!cnt) {
    for (int i = 1; i <= m; i += 2) a[++cnt] = i;
    return 1;
  }
  for (int i = 1; i <= a[1]; ++i) {
    for (auto x : vv[i]) sgt.update(1, 1, m, 1, x, -2);
    if (i < a[1] && i % 2 == a[1] % 2)
      a[++cnt] = i, sgt.update(1, 1, m, 1, i, 2);
  }
  sgt.update(1, 1, m, 1, a[1], 2);
  for (int i = 1; i < lst; ++i) {
    int p = a[i], q = a[i + 1];
    if (q - p <= 1) return 0;
    if (p % 2 == q % 2) {
      for (int j = p + 2; j < q; j += 2)
        a[++cnt] = j, sgt.update(1, 1, m, 1, j, 2);
      for (int j = p + 1; j <= q; ++j)
        for (auto x : vv[j])
          sgt.update(1, 1, m, 1, x, -2);
      sgt.update(1, 1, m, 1, q, 2);
    } else {
      static int tmp[kMaxN];
      for (int j = p; j <= q; ++j) tmp[j] = 0;
      for (int j = p + 1; j <= q; ++j) {
        sgt.update(1, 1, m, 1, j, 1 + (j == q));
        for (auto x : vv[j]) sgt.update(1, 1, m, 1, x, -2);
        auto p = sgt.query(1, 1, m, 1, j);
        if (p.first < 0) return 0;
        if (p.first == 0) {
          ++tmp[std::max(p.second, a[i])], --tmp[j];
        }
      }
      for (int j = p + 1; j <= q; ++j) tmp[j] += tmp[j - 1];
      int gap = -1;
      for (int j = p + 1; j < q; ++j) {
        if (j % 2 != p % 2 && !tmp[j]) { gap = j; break; }
      }
      if (!~gap) return 0;
      for (int j = p + 1; j <= q; ++j) sgt.update(1, 1, m, 1, j, -(1 + (j == q)));
      for (int j = p + 2; j < gap; j += 2)
        a[++cnt] = j, sgt.update(1, 1, m, 1, j, 2);
      for (int j = gap + 2; j < q; j += 2)
        a[++cnt] = j, sgt.update(1, 1, m, 1, j, 2);
      sgt.update(1, 1, m, 1, q, 2);
    }
  }
  for (int i = a[lst] + 2; i <= m; i += 2) a[++cnt] = i;
  std::sort(a + 1, a + 1 + cnt);
  return 1;
}

bool getres() {
  std::vector<int> vec;
  for (int i = 1; i <= n; ++i) vec.emplace_back(i);
  std::sort(vec.begin(), vec.end(), [&] (int x, int y) { return r[x] < r[y] || r[x] == r[y] && l[x] > l[y]; });
  std::set<int> st;
  for (int i = 1; i <= cnt; ++i) st.emplace(a[i]);
  for (auto i : vec) {
    auto it = st.lower_bound(l[i]);
    if (it != st.end() && *it <= r[i]) {
      res[i] = *it, st.erase(it);
    } else {
      return 0;
    }
  }
  return 1;
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> l[i] >> r[i];
  discrete();
  if (!getarr() || !getres()) return void(std::cout << "-1\n");
  for (int i = 1; i <= n; ++i) std::cout << unq[res[i]] << " \n"[i == n];
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
QOJ #10042. Scheduling 题解
https://sobaliuziao.github.io/2025/03/29/post/3a75670b.html
作者
Egg_laying_master
发布于
2025年3月29日
许可协议