[HDOJ6301] 18多校01 Distinct Values (莫队算法, 构造)

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6301

给出m个区间，要求构造一个指定区间内的数字不能相等，并且数字在$[1,n]$之间，求构造的字典序最小的方案。

首先给区间排个序，按照左端点小、右端点小的规则排。接下来维护两个指针L、R，从左到右往里塞，然后用类似莫队的更新方法去维护数列，同时维护目前可用的数字。 整体复杂度为$O(n+m)$。

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

using Node = struct {
  int l, r;
};
const int maxn = 100100;
int n, m, a[maxn];
Node p[maxn];
set<int> st;

signed main() {
  // freopen("in", "r", stdin);
  int T;
  scanf("%d", &T);
  while(T--) {
    st.clear();
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++) {
      scanf("%d%d",&p[i].l,&p[i].r);
    }
    sort(p+1, p+m+1, [](Node a, Node b) {
      return a.l == b.l ? a.r < b.r : a.l < b.l;
    });
    for(int i = 1; i <= n; i++) {
      st.insert(i);
      a[i] = 1;
    }
    int L = p[1].l, R = p[1].r;
    for(int i = L; i <= R; i++) {
      a[i] = *st.begin();
      st.erase(a[i]);
    }
    for(int i = 2; i <= m; i++) {
      while(L < p[i].l) {
        st.insert(a[L++]);
      }
      while(R < p[i].r) {
        if(R + 1 < p[i].l) R++;
        else {
          a[++R] = *st.begin();
          st.erase(a[R]);
        }
      }
    }
    for(int i = 1; i <= n; i++) {
      printf("%d%c", a[i], " \n"[i==n]);
    }
  }
  return 0;
}