传送门

这个题目有两种做法

差分约束

设s [ i ]表示前i个里面取数的个数
* s[b] – s[a – 1] >= ci
* s[k] – s[k – 1] >= 0 (任何k要比k-1取得多)
* s[k] – s[k – 1] <= 1 (任何数只能取一次)

然后建图跑，从第一个点开始跑最长路。
注意最后只能用spfa来跑，因为djistra无法处理反边权的情况。

#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);
        add(a, b + 1, c);
        m = max(m, max(a + 1, b + 1));
    }
    for(int i = 1; i <= m; i++)
    {
        add(i, i - 1, -1);
        add(i - 1, i, 0);
    }
    dji();
    cout << dis[m] << endl;
}

贪心

按区间右端点排序，优先选右边的，选到满足为止。直接线段树单点更新就可以，最多不会超过N次更新。用线段树优化区间查询的速度。

复杂度应该是NlogN的，但实际上跑得飞快。差分约束150ms，线段树只需要50ms。

#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(ask(1, a, b) < c[idx[i]])
        {
            while(vis[t]) t--;
            update(1, t, t, 1);
            vis[t] = 1;
            t--;
        }
    }
    cout << ask(1, 1, m);
}