D.小苯的数组最值
Link:Nowcoder
题目描述
小苯有一个长度为 $n$ 的数组 $a$，其中第 $i$ 个数字的值为 $a_i$。
现在小苯会对 $a$ 施加 $m$ 个魔法，具体的，第 $j$ 个魔法表示为 $(l_j, r_j, d_j)$，施法后会使得 $a_l, a_{l+1}, \cdots, a_r$ 这一段的数字都加上 $d_j$。
但身为见习魔法师的小苯法力并不稳定，具体来说这 $m$ 个魔法并不会全部施法成功，而是会随机且等概的失效一个魔法，只有 $m-1$ 个魔法施法成功，他想知道这样的情况下，数组 $a$ 最大值的期望是多少，请你帮他算一算吧。
输入描述:
每个测试文件内都包含多组测试数据。 第一行一个正整数 $T (1 \le T \le 1000)$，表示测试数据的组数。 接下来对于每组测试数据，输入包含 $m+2$ 行。 第一行两个整数 $n, m (1 \le n, m \le 5 \times 10^5)$，表示数组 $a$ 的长度，以及小苯的施法次数。 第二行 $n$ 个整数 $a_i (1 \le a_i \le 10^9)$，表示数组 $a$。 接下来 $m$ 行，每行三个正整数 $l_j, r_j (1 \le l_j \le r_j \le n, 0 \le d_j \le 10^9)$，描述每一个魔法。 （保证所有测试数据中 $n, m$ 的总和都不超过 $5 \times 10^5$。）
输出描述:
对于每个测试数据，输出一行一个整数表示数组的最大值对 $998244353$ 取模的值。 （分数取模的定义：可以证明，这个期望一定是一个有理数，如果写成 $p/q$ 的形式，你输出的 $a$ 需要保证 $a * q$ 对 $998244353$ 取模恰好等于 $p$。）
示例1
输入
1
2
3
4
5
6
7
8
1
3 3
1 1 1
1 1 2
2 2 3
3 3 4
输出
1
2
3
665496240
思路：
区间修改很明显该使用差分或者树状数组，但是此处还需要我们来找修改后的最大值。
如何维护最大值呢？
假如使用排序来进行查找时间复杂度将会达到 $(logN)^N$，总体的时间复杂度将达到 $N(logN)^N$ ，应该会超时