AcWing 296. 清理班次2

题目链接：​​传送门​​

洛谷上的​​P4644 [USACO05DEC]Cleaning Shifts​​​ 之前没发题解太高兴了
数据结构优化dp的例题
表示处理到处的最小花费
拿一个线段树维护最小值用来更新数组就好了

#include <bits/stdc++.h>
#define

using namespace std;
struct node {
  int l, r, w;
  friend bool operator < (const node a, const node b) {
    return a.r < b.r;
  }
}tree[A], e[A];
int n, l, r, f[A];
void build(int k, int l, int r) {
  tree[k].l = l; tree[k].r = r;
  if (l == r) {tree[k].w = f[l]; return;}
  int m = (l + r) >> 1;
  build(k << 1, l, m); build(k << 1 | 1, m + 1, r);
  tree[k].w = min(tree[k << 1].w, tree[k << 1 | 1].w);
}
void change(int k, int pos, int val) {
  if (tree[k].l == tree[k].r) {tree[k].w = val; return;}
  int m = (tree[k].l + tree[k].r) >> 1;
  if (pos <= m) change(k << 1, pos, val);
  else change(k << 1 | 1, pos, val);
  tree[k].w = min(tree[k << 1].w, tree[k << 1 | 1].w);
}
int ask(int k, int l, int r) {
  if (tree[k].l >= l and tree[k].r <= r) return tree[k].w;
  int m = (tree[k].l + tree[k].r) >> 1, ans = 0x3f3f3f3f;
  if (l <= m) ans = min(ans, ask(k << 1, l, r));
  if (r > m) ans = min(ans, ask(k << 1 | 1, l, r));
  return ans;
}

int main(int argc, char const *argv[]) {
  cin >> n >> l >> r; l++; r++;
  if (n == 1 and l == 1 and r == 1) return puts("1"), 0;
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &e[i].l, &e[i].r, &e[i].w), e[i].l++, e[i].r++;
  for (int i = l; i <= r; i++) f[i] = 0x3f3f3f3f;
  f[l] = 0; sort(e + 1, e + n + 1); build(1, l, r);
  for (int i = 1; i <= n; i++) {
    f[e[i].r] = min(f[e[i].r], ask(1, e[i].l - 1, e[i].r) + e[i].w);
    change(1, e[i].r, f[e[i].r]);
  }
  if (f[r] == 0x3f3f3f3f) puts("-1");
  else cout << f[r] << endl;
}