3832. [雅礼集训 2017 Day2] 水箱

【题目描述】

给出一个长度为 $n$ 宽度为 $1$ ，高度无限的水箱，有 $n - 1$ 个挡板将其分为 $n$ 个 $1 - 1$ 的小格，然后向每个小格中注水，水如果超过挡板就会溢出到挡板的另一边，这里的水是满足物理定律的（在无挡板阻拦的情况下会向低处流），现在有 $m$ 个条件 ($i$, $y$, $k$) ，表示从左到右数的第 $i$ 个格子中，在高度为 $y + 0.5$ 的地方是否有水， $k = 1$ 表示有水， $k = 0$ 表示没有水，请求出这 $m$ 个条件最多能同时满足多少个条件。本题有多组数据。

【输入格式】

第一行一个正整数 $T$ ，为数据组数。

第二行两个正整数 $n、m$ ，中间用空格隔开。

接下来一行 $n - 1$ 个整数，表示从左到右每一块隔板的高度。

接下来 $m$ 行，每行三个整数 $i 、 y 、 k$ ，表示一个条件。

【输出格式】

共 $T$ 行，每行对应一组数据的答案。

【样例1输入】

2
3 4
3 4
1 3 1
2 1 0
2 2 0
3 3 1
2 2
2
1 2 0
1 2 1

【样例1输出】

3
1

【样例2】

点击下载样例2

【数据规模与约定】

对于 $20\%$ 的数据， $n, m \leq 16$ ；

对于另外 $10\%$ 的数据，只存在指明某处有水的条件；

对于另外 $30\%$ 的数据， $n, m \leq 1000$ ；

对于 $100\%$ 的数据， $n, m \leq 10 ^ 5, T \leq 5$ 。