[SDCPC2023] Colorful Segments 线段树转移DP

Codeforces 链接​

  洛谷题目链接

# [SDCPC2023] Colorful Segments

## 题面翻译

**【题目描述】**

考虑数轴上的 $n$ 条线段，其中第 $i$ 条线段的左端点为 $l_i$，右端点为 $r_i$。每一条线段都被涂上了颜色，其中第 $i$ 条线段的颜色为 $c_i$（$0 \le c_i \le 1$）。颜色共有两种，$c_i = 0$ 代表一条红色的线段，而 $c_i = 1$ 代表一条蓝色的线段。

您需要选择若干条线段（可以不选择任何线段）。如果您选择的任意两条线段有重合，则这两条线段的颜色必须相同。

求选择线段的不同方案数。

称第 $i$ 条线段和第 $j$ 条线段有重合，若存在一个实数 $x$ 同时满足 $l_i \le x \le r_i$ 且 $l_j \le x \le r_j$。

称两种选择线段的方案是不同的，若存在一个整数 $1 \le k \le n$，满足第 $k$ 条线段在其中一个方案中被选择，而在另一个方案中没有被选择。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^5$）表示线段的数量。

对于接下来 $n$ 行，第 $i$ 行输入三个整数 $l_i$，$r_i$ 和 $c_i$（$1 \le l_i \le r_i \le 10^9$，$0 \le c_i \le 1$）表示第 $i$ 条线段的左右端点以及颜色。

保证所有数据 $n$ 之和不超过 $5 \times 10^5$。

**【输出格式】**

每组数据输出一行一个整数表示选择线段的不同方案数。由于答案可能很大，请将答案对 $998244353$ 取模后输出。

**【样例解释】**

对于第一组样例数据，您不能同时选择第 $1$ 和第 $2$ 条线段，也不能同时选择第 $2$ 和第 $3$ 条线段，因为它们有重合且颜色不同。

对于第二组样例数据，因为第 $2$ 条线段与第 $1$ 和第 $3$ 条线段都不重合，因此您可以任意选择线段。

## 题目描述

Consider $n$ segments on the number axis, where the left endpoint of the $i$-th segment is $l_i$ and the right endpoint is $r_i$. Each segment has a color where the color of the $i$-th segment is $c_i$ ($0 \le c_i \le 1$). There are two types of colors, where $c_i = 0$ indicates a red segment and $c_i = 1$ indicates a blue segment.

You need to choose some segments (you can also choose no segments at all). If any two chosen segments overlap, then they must have the same color.

Calculate the number of ways to choose segments.

We say segment $i$ overlaps with segment $j$, if there exists a real number $x$ satisfying both $l_i \le x \le r_i$ and $l_j \le x \le r_j$.

We say two ways of choosing segments are different, if there exists an integer $1 \le k \le n$ such that the $k$-th segment is chosen in one of the ways and is not chosen in the other.

## 输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$) indicating the number of segments.

For the following $n$ lines, the $i$-th line contains three integers $l_i$, $r_i$ and $c_i$ ($1 \le l_i \le r_i \le 10^9$, $0 \le c_i \le 1$) indicating the left and right endpoints and the color of the $i$-th segment.

It's guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^5$.

## 输出格式

For each test case output one line containing one integer indicating the number of ways to choose segments. As the answer may be large, please output the answer modulo $998244353$.

## 样例 #1

### 样例输入 #1

```
2
3
1 5 0
3 6 1
4 7 0
3
1 5 0
7 9 1
3 6 0
```

### 样例输出 #1

```
5
8
```

## 提示

For the first sample test case, you cannot choose the $1$-st and the $2$-nd segment, or the $2$-nd and the $3$-rd segment at the same time, because they overlap with each other and have different colors.

For the second sample test case, as the $2$-nd segment does not overlap with the $1$-st and the $3$-rd segment, you can choose them arbitrary.

按线段的 r 端点排序 对两种颜色建两颗不同的线段树 ，枚举当前线段，设当前线段颜色是 A， 当前线段如果不选的话， 当前线段的 l 左边的颜色B的线段全部都能转移到当前的 r 端点处 ，当前答案转移到颜色为A的线段树， 如果选择选当前的线段的话 ，当前线段的l  左边的颜色B的线段全部 * 2， 因为颜色B可以选或者不选，当前答案转移到颜色为B的线段树

最后答案即为某一种颜色全部加起来，注意最开始从0开始往右边转移