提交记录

代码

#include <bits/stdc++.h>
#define int long long
const int MAXN = 15e4 + 20;

int N;
struct sequence
{
    int Start, End;

    friend bool operator < (const sequence &a, const sequence &b)
    {
        if(a.End != b.End)
        {
            return a.End < b.End;
        }else {
            return a.Start < b.Start;
        }
    }
}Seq[MAXN];

/*
状态定义 : dp[i] 表示以 i 为右节点的区间最长序列
状态转移方程 : dp[i] = 在所有 j < 当前区间左端点中 max{dp[j] = 当前区间的长度}
dp[0] = 0
从左往右计算
O(n ^ 2) 加上树状数组优化前面的最大值
*/
int dp[MAXN];

/*树状数组*/
class BinaryIndexTree
{
    private:

    public:
    int lowerbit(int x)
    {
        return x & -x;
    }
    int Tree[3000005];
    int find_max(int End)
    {
        int Ans = 0;
        while(End)
        {
            Ans = std::max(Ans, Tree[End]);
            End -= lowerbit(End);
        }

        return Ans;
    }

    void update(int Pos, int Val)
    {
        while(Pos <= (300005))
        {
            Tree[Pos] = std::max(Val, Tree[Pos]);
            Pos += lowerbit(Pos);
        }
    }
}BIT;

signed main()
{
    scanf("%lld", &N);
    for(int i = 1; i <= N; i++)
    {
        scanf("%lld %lld", &Seq[i].Start, &Seq[i].End);
        Seq[i].Start += 1;
        Seq[i].End += 1;
    }
    std::sort(Seq + 1, Seq + N + 1);


    dp[1] = Seq[1].End - Seq[1].Start + 1;
    BIT.update(Seq[1].End, dp[1]);
    for(int i = 2; i <= N; i++)
    {
        dp[Seq[i].End] = BIT.find_max(Seq[i].Start - 1) + (Seq[i].End - Seq[i].Start + 1);
        BIT.update(Seq[i].End, dp[Seq[i].End]);
    }

    int ans = 0;
    for(int i = 1; i <= Seq[N].End; i++)
    {
        ans = std::max(ans, dp[i]);
    }

    printf("%lld", ans);

    return 0;
}