## 传送门

### 差分约束

* s[b] – s[a – 1] >= ci
* s[k] – s[k – 1] >= 0 (任何k要比k-1取得多)
* s[k] – s[k – 1] <= 1 (任何数只能取一次)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 233;
int h[maxn], e[maxn], pre[maxn], val[maxn], cnt;
void add(int u, int v, int w)
{
e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt;
}
int dis[maxn], vis[maxn];
void dji()
{
memset(dis, -1, sizeof dis);
memset(vis, 0, sizeof vis);
queue<int> q;
dis[0] = 0;
q.push(0); vis[0] = 1;
while(q.size())
{
int x = q.front(); q.pop(); vis[x] = 0;
for(int i = h[x]; i; i = pre[i])
{
int y = e[i], z = val[i];
if(dis[y] < dis[x] + z)
{
dis[y] = dis[x] + z;
if(!vis[y])
{
q.push(y);
vis[y] = 1;
}
}
}
}
}
int main()
{
int n = 0, m = 0;
cin >> n;
for(int i = 1; i <= n; i++)
{
int a, b, c;
scanf("%d%d%d",&a, &b, &c);
m = max(m, max(a + 1, b + 1));
}
for(int i = 1; i <= m; i++)
{
}
dji();
cout << dis[m] << endl;
}


### 贪心

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
const int maxn = 1e5 + 233;
pair<int,int> itv[maxn];
int c[maxn], idx[maxn];
struct SegNode{
int l,r,dat,mk;
#define l(x) t[x].l
#define r(x) t[x].r
#define dat(x) t[x].dat
#define mk(x) t[x].mk
}t[maxn * 4];
void build(int p, int l, int r)
{
l(p) = l, r(p) = r;
if(l == r) return;
int mid = (l + r) >> 1;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
}
void spr(int p)
{
if(mk(p))
{
dat(ls(p)) = r(ls(p)) - l(ls(p)) + 1;
dat(rs(p)) = r(rs(p)) - l(rs(p)) + 1;
mk(ls(p)) = mk(p);
mk(rs(p)) = mk(p);
mk(p) = 0;
}
}
void update(int p, int l, int r, int v)
{
if(l <= l(p) && r >= r(p))
{
dat(p) = (r - l + 1);
mk(p) = v;
return;
}
spr(p);
int mid = (l(p) + r(p)) >> 1;
if(l <= mid) update(ls(p), l, r, v);
if(r > mid) update(rs(p), l, r, v);
dat(p) = dat(ls(p)) + dat(rs(p));
}
int ask(int p, int l, int r)
{
if(l <= l(p) && r >= r(p)) return dat(p);
spr(p);
int mid = (l(p) + r(p)) >> 1;
int res = 0;
if(l <= mid) res += ask(ls(p), l, r);
if(r > mid) res += ask(rs(p), l, r);
return res;
}
bool cmp(const int &x, const int &y)
{
return itv[x].second < itv[y].second;
}
int vis[maxn];
int main()
{
int n, m = 0;
cin >> n;

for(int i = 1; i <= n; i++)
{
scanf("%d%d%d",&itv[i].first, &itv[i].second, &c[i]);
m = max(m, max(itv[i].first, itv[i].second));
idx[i] = i;
}
m++;
sort(idx + 1, idx + 1 + n, cmp);
build(1, 1, m);
for(int i = 1; i <= n; i++)
{
int a = itv[idx[i]].first  + 1, b = itv[idx[i]].second + 1;
int t = b;
{
while(vis[t]) t--;
update(1, t, t, 1);
vis[t] = 1;
t--;
}
}
}