CF1389F [Bicolored Segments] 题解

前言：

前置知识：线段树(维护区间修改，区间查询最大值，单点覆盖) + $dp$

这道题目挺有意思的，在经过许多删改后，写了一份比较容易看懂的代码。

这篇题解我将提供两个版本，一种是详细版（给完全没有思路的同学看的，位于文末,有思路讲解，一步一步分析题目）

另外一种是精简版，大概的简述做法，您可以根据自己的情况选择看哪一种。

题意转述：

每条线段为黑色或白色。我们称一对线段不好当且仅当颜色不同且有公共点。

求一个最大的子集(包含的线段最多)使得不存在不好的线段对。

精简版:

通过将线段按照右端点从小到大排序依次加入去除后效性。同时要离散化。

状态设立： $dp[i][j][0/1]$
状态转移方程:(假设当前处理到的线段是线段 $i$ )

假设当前这条线段的左端点是 $l_i$ 右端点是 $r_i$ 。

（因为考虑到黑白是同样的做法，就假定当前这条线段是黑的吧，对应 $dp[i][r_i][1]$ ）

不选当前线段:

$dp[i][r_i][1] = dp[i - 1][r_{i-1}][1]$

选当前线段:

假设上一条被选择的白色线段的右端点是 $r_j$

根据题目的意思，左右端点都在 $[r_j + 1$ , $r_i]$ 这里面的所有黑色线段显然是都可以选择的。

状态转移方程: $dp[i][r_i][1] = max(dp[k][r_k][0] + Clac(r_k + 1,r_i))$

ps.这里的 $k < i$ 并且 $r_k < l_i$ (其右端点不能在这条线段的左端点及后面), $Clac(r_k + 1,r_i)$ 表示左右端点都在 $[r_k + 1,r_i]$ 这段区间内的黑色线段。

考虑到如何提前计算 $Clac(r_k + 1,r_i)$ ,进行状态转移前就先将 $r_k < l_i$ 的所有 $dp[k][r_k][0]$ 都加上一个 $1$ 。

然后方程就变成了 $dp[i][r_i][1] = max(dp[k][r_k][0])$ ( $k < i$ 并且 $r_k < l_i$ )

发现要实现区间加法，区间找最大值，单点修改，使用线段树维护即可。

Code

// Memory Limit: 250 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 50;
int n;
map <int,int> mp;
int N[MAXN * 2];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar() ;
    for( ; ch > '9' || ch < '0' ; ch = getchar()) ;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

struct Segment {
    int l,r,ty;
    void init(){l = read() , r = read() , ty = read() ;return ;}
    bool operator < (const Segment &P) { return r < P.r; }//重载了运算符
} S[MAXN];

struct SegmentTree { //两个线段树，一个是维护黑色的，为线段树B，另外一个维护白色的，为线段树W
    int Max[MAXN * 8],laz[MAXN * 8],L[MAXN * 8],R[MAXN * 8];
    void build(int x,int l,int r) {//建树
        L[x] = l , R[x] = r;
        Max[x] = laz[x] = 0;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        build(x << 1 , l , mid);
        build(x << 1 | 1 , mid + 1 , r);
        return ;
    }
    void update(int x,int k) {
        laz[x] += k , Max[x] += k;
        return ;
    }
    void pushdown(int x) {
        if(laz[x] == 0) return ;
        update(x << 1 , laz[x]);
        update(x << 1 | 1 , laz[x]);
        laz[x] = 0;
        return ;
    }
    int GetMax(int x,int l,int r) {//区间最大值
        int M = 0;
        if(L[x] >= l && R[x] <= r) return Max[x];
        pushdown(x);
        int mid = (L[x] + R[x]) >> 1;
        if(l <= mid) M = max(M , GetMax(x << 1 , l , r) );
        if(r  > mid) M = max(M , GetMax(x << 1 | 1 , l , r) );
        return M;
    }
    void add(int x,int l,int r,int k) {//区间加法
        if(L[x] >= l && R[x] <= r) {
            update(x , k);
            return ;
        }
        pushdown(x);
        int mid = (L[x] + R[x]) >> 1;
        if(l <= mid) add(x << 1 , l , r , k);
        if(r  > mid) add(x << 1 | 1 , l , r , k);
        Max[x] = max(Max[x << 1] , Max[x << 1 | 1]);
        return ;
    }
    void change(int x,int pos,int k) { //单点修改
        if(L[x] == pos && R[x] == pos) {
            Max[x] = k;
            return ;
        }
        pushdown(x);
        int mid = (L[x] + R[x]) >> 1;
        if(pos <= mid) change(x << 1 , pos , k);
        else change(x << 1 | 1 , pos , k);
        Max[x] = max(Max[x << 1] , Max[x << 1 | 1]);
        return;
    }
} B,W;

void Discretization() {//离散化
    int len = 0;
    for(int i = 1 ; i <= n ; i ++) 
    N[++len] = S[i].l , N[++len] = S[i].r;
    sort(N + 1 , N + 1 + len);
    for(int i = 1 ; i <= len ; i ++) mp[N[i]] = i + 1;
   //因为S[i].l离散化后-1可能是0，所以我在离散化的时候就将每一个
   //S[i].l 以及S[i].r + 1 了，就是上面的mp[N[i]] = i + 1;
    for(int i = 1 ; i <= n ; i ++)
    S[i].l = mp[S[i].l] , S[i].r = mp[S[i].r];
    return ;
}

int main() {
    n = read();
    for(int i = 1 ; i <= n ; i ++) S[i].init();//读入而已，为了看起来简便就这么写了
    Discretization();//离散化
    sort(S + 1 , S + 1 + n);//按照右端点从小到大排序，重载了运算符
    B.build(1 , 1 , 2 * n + 1);
    W.build(1 , 1 , 2 * n + 1);
    for(int i = 1 ; i <= n ; i ++) {
        if(S[i].ty == 1) {//代表是白***.add(1 , 1 , S[i].l - 1 , 1);//提前加上
            int Max = W.GetMax(1, 1 , S[i].r);//假设不选，求一个最大值
            int op = B.GetMax(1 , 1 , S[i].l - 1);//假设选择，求一个最大值
            W.change(1 , S[i].r , max(op,Max));//最后当前点就修改为选择以及不选择的max就行了
        }
        else {//否则是黑色，操作同上，只不过 "B"改成了"W"，"W"改成了"B"
            W.add(1 , 1 , S[i].l - 1 , 1);
            int Max = B.GetMax(1, 1 , S[i].r);
            int op = W.GetMax(1 , 1 , S[i].l - 1);
            B.change(1 , S[i].r , max(op,Max));
        }
    }
    cout << max(B.GetMax(1 , 1 , n * 2 + 1),W.GetMax(1 , 1 , n * 2 + 1));
    return 0;
}

详细版

引入:

想必大家在初学贪心的阶段都做过这么一道题目：

从若干线段中选出若干条不相交的线段，求最多选出的线段数

本题其实就是由这个题目“进化”来的。

$Ask$ ：这道题还能按照原来的题目进行贪心吗？

$Answer$ : 不能说完全一样吧，但是用到了一部分贪心思想。

题目分析

要保证动态规划没有后效性。

一个非常显而易见的做法就是我们按照右端点从小到大加入就可以去除掉后效性，所以这个题目可以使用动态规划。

状态的设置:

我的思考过程(也就是如何得出状态设置的)：

一维可以吗？

$dp[i]$ 表示前 $i$ 个后能获得的最多线段数?

这个显然不行，因为不能进行转移，我并不知道最后一个是放入的是黑色还是白色，以及它的右端点坐标是哪里。

二维可以吗？

$dp[i][j][0/1]$ 表示考虑前 $i$ 个， $j$ 表示最后一个放入的线段的右端点， $0/1$ 就表示最后放入的线段的颜色。

好像时间上过不去啊（空间上是没有问题的，因为第一维可以滚动掉，第二维可以进行离散化）。

时间上的优化

从状态转移方程着手:

假设当前这条线段的左端点是 $l_i$ 右端点是 $r_i$ 。

如果不选择当前线段:

$dp[i][r_i][0] = dp[i - 1][r_i][0] , dp[i][r_i][1] = dp[i - 1][r_i][1]$

如果选择当前线段:

（因为考虑到黑白是同样的做法，就假定当前这条线段是黑的吧，对应 $dp[i][r_i][1]$ ）

那么我们就需要知道上一条被选择的白色线段的右端点是在哪一个位置，假设是 $r_j$

左右端点都在 $[r_j + 1$ , $r_i]$ 这里面的所有黑色线段显然是都可以选择的。就很容易写出状态转移方程:

$dp[i][r_i][1] = max(dp[k][r_k][0] + Clac(r_k + 1,r_i))$

ps.这里的 $k < i$ 并且 $r_k < l_i$ (其右端点不能在这条线段的左端点及后面)， $Clac(r_k + 1,r_i)$ 表示左右端点都在 $[r_k + 1,r_i]$ 这段区间内的黑色线段。

时间复杂度瓶颈是在枚举所有的 $k < i$ 求 $max(dp[k][r_k][0] + Clac(r_k + 1,r_i))$ 的过程。

这里的 $Clac(r_k + 1 , r_i)$ 是跟 $r_k$ 有关的，这给我们带来了很大的麻烦，考虑如何使得其与 $r_k + 1$ 无关。

可以事先在转移之前将 $dp[k][r_k][0]$ 提前加上 $Clac(r_k + 1,r_i))$ 。

因为枚举的是 $k < i$ 并且 $r_k < l_i$ ，所以我们加入一条线段的时候就先将 $r_k < l_i$ 的所有 $dp[k][r_k][0]$ 都加上一个 $1$ 。

这样子 $dp$ 状态转移的时候只需要找 $max(dp[k][r_k][0])$ ( $r_k < l_i$ ) ，这个方程是一个经典的状态转移，可以用单调队列/ 线段树优化。

但是考虑到我们要将 $r_k < l_i$ 的所有 $dp[k][r_k][0]$ 都加上一个 $1$ ，所以只能使用线段树。

然后将所有做法转移到两棵线段树上：

一棵线段树维护的是最后选择白色线段的 $dp$ ，另外一棵就维护最后选择黑色线段的 $dp$ 。

线段树中的节点 $[j,j]$ 就表示 $dp[i][j][0/1]$ ( $i$ 的那一维在枚举的时候就滚动掉了 )

还是假设当前是处理黑色线段。

首先将白色的那棵对应的对应区间 $[1,l_i - 1]$ 全部加一(对应上面的做法就是将 $dp[k][r_k][0](r_k < l_i)$ 加一)。

如果是不选择的话，那么我们就无需修改黑线段树的状态，也就是当前黑线段树的全局最大值 $Max$ ，如果选择的话，实际上就是目前白线段树中 $[1,l_i - 1]$ 中的最大值。

取选择/不选择的最大值对于当前黑线段树上的点 $[r_i,r_i]$ 进行单点修改。

将整个 $dp$ 完全用线段树来实现，最后的答案就是线段树中的最大值。

实现的操作为：区间加法，区间找最大值，单点修改。