11332: 【原1332】行道树

题目描述

author: 陈昕昀原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1332

Description

一条路上原本种了n棵小树苗，第i棵树苗用三个正整数l(i),r(i),c(i)表示，[l(i),r(i)]表示该树苗长大后能够覆盖道路的区间，l(i)<r(i),c(i)表示该树苗的种类。然而现在发现了一个严峻的问题：如果两棵树覆盖的区间重叠了（在端点处不算重叠），那么不仅对树苗的成长不利，也影响美观。于是我们不得不砍掉一些树来保证剩余树苗长大后覆盖的区间两两不重叠。当然我们希望留下最多树苗，求出这一最大值。

除此之外，我们还希望知道在保留最多树苗的情况下，有多少种本质不同的保留方案。设两个方案中，按r的值从小到大排序后，保留的树苗标号分别为i1，i2，…，im以及j1，j2，…，jm，则两个方案本质不同当且仅当存在k，使得c(ik)!=c(jk)。

Input Format

第一行包含两个整数n和L，表示树苗棵数与路的坐标范围。

接下来n行，每行三个正整数l，r，c，含义见题面。

Output Format

输出共两行。

第一行输出最多保留树苗棵数。

第二行输出方案数。这样的方案数可能很多，将方案数mod 1000000009输出即可。

Sample Input

Sample Output

2
2

Constraints

前3个数据点满足n<=20

4、5、6数据点满足n<=2000，且ci恒等于1.

7、8数据点满足n<=100000，且ci恒等于1.

9、10数据点满足n<=2000。

对于所有数据，1<=L<=100000，1<=ci<=n

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！