No Abstract.

Des.

There are several segments on a line, with $l$ and $r$ as end points.

Every time choose the shortest line (might be with a length of 0), and erase it. But once a part of line is erased, it won’t be calculated in other segments’ lengths.

It is guaranteed that there’s won’t be any segment whole in another.

Sol.

Seems that we can use a Segment Tree to maintain the shortest line, but as in description, the end points of segments are dynamic.

Notice that after a segment is erased, some other segments’ $l$ points or $r$ points will be the same, and always keep the same from then on. So we can have two UFS for $l$ and $r$ separately, and merge the sets in an operation. All elements in a set will decrease the same length after an operation, that’s what we can deal with the help of Segment Tree.

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
#include <bits/stdc++.h>
#define fir first
#define sec second

using namespace std;
typedef pair<int, int> pii;

const int maxn = 3e+5 + 5;
const int inf = (1 << 30) - 1;

pii w[maxn << 2]; int tag[maxn << 2];
int n, t;
int l[maxn], r[maxn];
int lst[maxn], rst[maxn];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline void pushup(const int &cur) {
  w[cur] = min(w[cur << 1], w[cur << 1|1]);
}
inline void pushdown(const int &cur) {
  if (tag[cur]) {
    w[cur << 1].fir += tag[cur];
    w[cur << 1|1].fir += tag[cur];
    tag[cur << 1] += tag[cur];
    tag[cur << 1|1] += tag[cur];
    tag[cur] = 0;
  }
}
void build(int cur, int L, int R) {
  if (L == R) {
    w[cur] = pii(r[L] - l[L], L);
    return;
  }
  int mid = (L + R) >> 1;
  build(cur << 1, L, mid);
  build(cur << 1|1, mid + 1, R);
  pushup(cur);
}
void update(int cur, int L, int R, int x, int y, int v) {
  if (x > y) return;
  if (R < x || y < L) return;
  if (x <= L && R <= y) {
    tag[cur] += v;
    w[cur].fir += v;
    return;
  }
  pushdown(cur);
  int mid = (L + R) >> 1;
  if (x <= mid) update(cur << 1, L, mid, x, y, v);
  if (y > mid) update(cur << 1|1, mid + 1, R, x, y, v);
  pushup(cur);
}
int find(int *fa, int x) {
  return fa[x] == x ? x : fa[x] = find(fa, fa[x]);
}
inline void swipel(int id, int vr) {
  int fx = find(lst, id);
  if (l[fx] >= vr) return;
  int last = id;
  while (1) {
    update(1, 1, n, last + 1, fx, l[fx] - vr);
    int nfx = find(lst, fx + 1);
    if (l[nfx] >= vr) break;
    else {
      lst[fx] = nfx;
      last = fx;
      fx = nfx;
    }
  }
  l[fx] = vr;
}
inline void swiper(int id, int vl) {
  int fx = find(rst, id);
  if (r[fx] <= vl) return;
  int lst = id;
  while (1) {
    update(1, 1, n, fx, lst - 1, vl - r[fx]);
    int nfx = find(rst, fx - 1);
    if (r[nfx] <= vl) break;
    else {
      rst[fx] = nfx;
      lst = fx;
      fx = nfx;
    }
  }
  r[fx] = vl;
}

int main() {
  t = rd(); n = rd();
  for (int i = 1; i <= n; ++i)
    l[i] = rd(), r[i] = rd();
  l[n + 1] = r[n + 1] = inf;
  for (int i = 0; i <= n + 1; ++i)
    lst[i] = rst[i] = i;
  build(1, 1, n);
  for (int i = 1; i <= n; ++i) {
    pii u = w[1];
    printf("%d\n", u.sec);
    int curl = l[find(lst, u.sec)], curr = r[find(rst, u.sec)];
    swipel(u.sec, curr);
    swiper(u.sec, curl);
    update(1, 1, n, u.sec, u.sec, inf);
    // printf("%d %d\n", w[1].fir, w[1].sec);
  }
  return 0;
}