Segment Covering

题意翻译

给定 $ n $ 个区间 $ [x_i, y_i] $，保证所有区间均不同。令 $ f(l, r) $ 表示从 $ n $ 个区间中选择偶数个区间使得其求并集后恰为 $ [l, r] $ 的方案数，令 $ g(l, r) $ 表示从 $ n $ 个区间中选择奇数个区间使得其求并集后恰为 $ [l, r] $ 的方案数。给定 $ q $ 组询问 $ [l_i, r_i] $，输出 $ f(l_i, r_i) - g(l_i, r_i) $，对 $ 998244353 $ 取模。

题目描述

ChthollyNotaSeniorious gives DataStructures a number axis with $ m $ distinct segments on it. Let $ f(l,r) $ be the number of ways to choose an even number of segments such that the union of them is exactly $ [l,r] $ , and $ g(l,r) $ be the number of ways to choose an odd number of segments such that the union of them is exactly $ [l,r] $ . ChthollyNotaSeniorious asked DataStructures $ q $ questions. In each query, ChthollyNotaSeniorious will give DataStructures two numbers $ l, r $ , and now he wishes that you can help him find the value $ f(l,r)-g(l,r) $ modulo $ 998\,244\,353 $ so that he wouldn't let her down.

输入输出格式

输入格式

The first line of input contains two integers $ m $ ( $ 1 \leq m \leq 2 \cdot 10^5 $ ) and $ q $ ( $ 1 \leq q \leq 2 \cdot 10^5 $ ) — the number of segments and queries, correspondingly. The $ i $ -th of the next $ m $ lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \leq x_i < y_i \leq 10^9 $ ), denoting a segment $ [x_i, y_i] $ . It is guaranteed that all segments are distinct. More formally, there do not exist two numbers $ i, j $ with $ 1 \le i < j \le m $ such that $ x_i = x_j $ and $ y_i = y_j $ . The $ i $ -th of the next $ q $ lines contains two integers $ l_i $ and $ r_i $ ( $ 1 \leq l_i < r_i \leq 10^9 $ ), describing a query.

输出格式

For each query, output a single integer — $ f(l_i,r_i)-g(l_i,r_i) $ modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

4 2
1 3
4 6
2 4
3 5
1 4
1 5

输出样例 #1

1
0

说明

In the first query, we have to find $ f(1, 4) - g(1, 4) $ . The only subset of segments with union $ [1, 4] $ is $ \{[1, 3], [2, 4]\} $ , so $ f(1, 4) = 1, g(1, 4) = 0 $ . In the second query, we have to find $ f(1, 5) - g(1, 5) $ . The only subsets of segments with union $ [1, 5] $ are $ \{[1, 3], [2, 4], [3, 5]\} $ and $ \{[1, 3], [3, 5]\} $ , so $ f(1, 5) = 1, g(1, 5) = 1 $ .

**题目大意：**

给定一个数轴上有m个不同的区间。定义函数f(l, r)为从这些区间中选择偶数个区间，并集恰好为[l, r]的方案数；定义函数g(l, r)为从这些区间中选择奇数个区间，并集恰好为[l, r]的方案数。给定q组询问，每组询问是两个数字l, r，需要输出f(l, r) - g(l, r)对998244353取模的结果。

**输入输出数据格式：**

**输入格式：**
- 第一行包含两个整数m和q，分别表示区间的数量和询问的数量。
- 接下来m行，每行包含两个整数x_i和y_i，表示一个区间[x_i, y_i]。
- 再接下来q行，每行包含两个整数l_i和r_i，表示一个询问。

**输出格式：**
- 对于每个询问，输出一个整数，表示f(l_i, r_i) - g(l_i, r_i)对998244353取模的结果。

**输入输出样例：**

**输入样例 #1：**
```
4 2
1 3
4 6
2 4
3 5
1 4
1 5
```

**输出样例 #1：**
```
1
0
```**题目大意：** 给定一个数轴上有m个不同的区间。定义函数f(l, r)为从这些区间中选择偶数个区间，并集恰好为[l, r]的方案数；定义函数g(l, r)为从这些区间中选择奇数个区间，并集恰好为[l, r]的方案数。给定q组询问，每组询问是两个数字l, r，需要输出f(l, r) - g(l, r)对998244353取模的结果。 **输入输出数据格式：** **输入格式：** - 第一行包含两个整数m和q，分别表示区间的数量和询问的数量。 - 接下来m行，每行包含两个整数x_i和y_i，表示一个区间[x_i, y_i]。 - 再接下来q行，每行包含两个整数l_i和r_i，表示一个询问。 **输出格式：** - 对于每个询问，输出一个整数，表示f(l_i, r_i) - g(l_i, r_i)对998244353取模的结果。 **输入输出样例：** **输入样例 #1：** ``` 4 2 1 3 4 6 2 4 3 5 1 4 1 5 ``` **输出样例 #1：** ``` 1 0 ```