Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。

原文链接：https://www.codein.icu/cf1389f/

题意

定义坏对为：两个线段相交且颜色不同。求最多选出多少个线段，能保证没有坏对。

解法

虽然两个颜色让人很容易想到二分图之类的东西，但这题更易理解的应该是动态规划做法。
先对坐标离散化一下方便处理。
定义 $f(i,j,k)$ 为 $[1,i]$ 的坐标区间中，保证 $[j + 1,i]$ 的颜色为 $k$ 能选出的最多线段。那么 $[1,j]$ 颜色与 $k$ 相反。
$f(i,j,k) = f(i-1,j,k) + \sum (L > j,R = i)$，即加入 $i$ 点后，贡献计入右端点为 $i$ 且颜色符合条件的线段。
首先 $i$ 可以滚动掉，而 $\sum (L > j,R = i)$，对于某一段连续的 $j$，值都是相同的，可以考虑用区间修改的数据结构维护。
这里选择使用线段树来维护。
对于 $R = i$ 的颜色为 $k$ 的线段，满足条件 $L > j$ 的区间为 $[1,L – 1]$，每次对区间 $[1,L – 1]$ 加 $1$ 即可转移。容易发现，每个线段只会进行一次区间修改操作，复杂度 $O(n\log n)$。
理论上要求 $j < i$，然而如果 $f(i,i-1,k)$ 从 $f(i-1,i-1,k)$ 来转移呢？因此需要给 $f(i,i,k)$ 也赋值，即颜色任意的情况，$f(i,i,k) = \max[f(i,j,k),f(i,j,!k)](j < i)$。
维护全局最大值即可用于更新 $f(i,i,k)$。
实现好像没啥细节。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <vector>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 4e5 + 100;
int n;
struct seg
{
    int l, r, t;
} S[maxn];
int H[maxn], cnt;
vector<pair<int, int> > V[maxn];
struct SegmentTree
{
    int maxx[maxn << 2], tag[maxn << 2];
    void pushdown(int p)
    {
        if (!tag[p]) return;
        maxx[p << 1] += tag[p], maxx[p << 1 | 1] += tag[p];
        tag[p << 1] += tag[p], tag[p << 1 | 1] += tag[p];
        tag[p] = 0;
    }
    void add(int l, int r, int p, int ll, int rr, int k)
    {
        if (ll > rr) return;
        if (l >= ll && r <= rr)
        {
            maxx[p] += k;
            tag[p] += k;
            return;
        }
        pushdown(p);
        int mid = l + r >> 1;
        if (ll <= mid) add(l, mid, p << 1, ll, rr, k);
        if (rr > mid) add(mid + 1, r, p << 1 | 1, ll, rr, k);
        maxx[p] = max(maxx[p << 1], maxx[p << 1 | 1]);
    }
    void modify(int l, int r, int p, int pos, int k)
    {
        if (l == r) return (void)(tag[p] = 0, maxx[p] = k);
        pushdown(p);
        int mid = l + r >> 1;
        if (pos <= mid) modify(l, mid, p << 1, pos, k);
        else modify(mid + 1, r, p << 1 | 1, pos, k);
        maxx[p] = max(maxx[p << 1], maxx[p << 1 | 1]);
    }
} T[2];
int main()
{
    read(n);
    H[++cnt] = 0;
    for (int i = 1; i <= n; ++i) read(S[i].l), read(S[i].r), read(S[i].t), H[++cnt] = S[i].l, H[++cnt] = S[i].r;
    sort(H + 1, H + 1 + cnt), cnt = unique(H + 1, H + 1 + cnt) - H - 1;
    for (int i = 1; i <= n; ++i)
    {
        S[i].l = lower_bound(H + 1, H + 1 + cnt, S[i].l) - H;
        S[i].r = lower_bound(H + 1, H + 1 + cnt, S[i].r) - H;
        V[S[i].r].push_back(make_pair(S[i].l, S[i].t - 1));
    }
    for (int i = 1; i <= cnt; ++i)
    {
        for (vector<pair<int, int> >::iterator it = V[i].begin(); it != V[i].end(); ++it)
        {
            int L = it->first, k = it->second;
            T[k].add(1, cnt, 1, 1, L - 1, 1);
        }
        int maxnum = max(T[0].maxx[1], T[1].maxx[1]);
        T[0].modify(1, cnt, 1, i, maxnum);
        T[1].modify(1, cnt, 1, i, maxnum);
    }
    printf("%d\n", max(T[0].maxx[1], T[1].maxx[1]));
    return 0;
}