1008. H. Mode

题目描述

给定一个长度为 (n) 的颜色序列 (a_1,a_2,\ldots,a_n)，每个位置的颜色均为 (1) 到 (K) 之间的整数。

接下来按时间顺序给出 (m) 个操作，第 (i) 个操作对应一个区间 ([l_i,r_i])。考虑这个操作时，你可以选择跳过它，也可以选择执行它。

执行区间 ([l,r]) 时，如果存在一种颜色 (c)，满足它在当前序列 (a_l,a_{l+1},\ldots,a_r) 中的出现次数严格大于区间长度的一半，就将区间内的所有位置全部改成颜色 (c)。如果不存在这样的颜色，则序列不会发生变化。

每个操作均可独立选择执行或跳过，因此共有 (2^m) 种选择方案。求这些方案一共能够得到多少种互不相同的最终颜色序列。答案对 (998244353) 取模。

保证对于任意两个操作区间，它们要么没有公共位置，要么其中一个包含另一个。两个区间可以完全相同。

样例解释

能够得到的四种最终序列分别为：

2 2 1 1 1
1 1 1 1 1
2 2 2 1 1
2 2 2 2 2

数据范围

• (1\le T\le 10)
• (1\le n,m\le 2\times 10^5)
• (1\le K\le 5)
• (1\le a_i\le K)
• (1\le l_i\le r_i\le n)
• 所有测试数据的 (n) 之和不超过 (4\times10^5)
• 所有测试数据的 (m) 之和不超过 (4\times10^5)

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

第一行包含三个整数 (n,m,K)。

第二行包含 (n) 个整数 (a_1,a_2,\ldots,a_n)，表示初始颜色序列。

接下来 (m) 行，第 (i) 行包含两个整数 (l_i,r_i)，表示第 (i) 个操作。操作必须按照输入顺序依次考虑。

输出格式

对于每组测试数据，输出一行一个整数，表示不同最终颜色序列的数量对 (998244353) 取模后的结果。

样例输入

1
5 3 2
2 2 1 1 1
1 5
1 3
1 5

样例输出

4

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1008