Boring Segments-CF教育场112.尺取+线段树

5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3

3

1 10
1 10 23

0

#define mid ((l + r) >> 1)
int t[maxn], tg[maxn];
struct seg {
  int l, r, w;
  bool friend operator <(seg a, seg b){
    return a.w < b.w;
  }
} seg[maxn];
int n, m;
void Modify(int rt, int l, int r, int L, int R, int val)
{
  if (l >= L && r <= R) {
    t[rt] += val;
    tg[rt] += val;
    return;
  }
  if (L <= mid) Modify(rt << 1, l, mid, L, R, val);
  if (R > mid) Modify(rt << 1 | 1, mid + 1, r, L, R, val);
  t[rt] = tg[rt] + min(t[rt << 1], t[rt << 1 | 1]);
  return;
}
int main()
{
  n = read, m = read;
  for (int i = 1; i <= n; i++) {
    seg[i].l = read, seg[i].r = read, seg[i].w = read;
  }
  sort(seg + 1, seg + 1 + n);
  int l = 1, ans = 1 << 30;
  for (int r = 1; r <= n; r++) {
    Modify(1, 1, m - 1, seg[r].l, seg[r].r - 1, 1);
    while (t[1]) {
      ans = min(ans, seg[r].w - seg[l].w);
      Modify(1, 1, m - 1, seg[l].l, seg[l].r - 1, -1);
      l++;
    }
  }
  cout << ans << endl;
  return 0;
}
/**
 **/