1407. [SHOI 2015]Discover Water Tank

【题目描述】

一个水箱里生活着许多青蛙，但它们不知道水箱里到底有多少水。

水箱的高度无限，但底部很窄。水箱（底面）的长度是N，但宽度仅为1.

水箱的底部有N-1块隔板，从而把它分成N个部分，每个部分的底面都是1*1。隔板的高度不同。隔板能阻挡水，但高于隔板的水当然可以自由流动，同我们的常识相符。

青蛙国王想了解水箱的更多细节，因此虵选取了M个位置，并派人查看这些位置是否被水淹没。

例如，每次他选取(x,y)，检查水箱从左到右第x个部分，高度为y+0.5的位置是否被淹没。

现在国王有了M个结果，但他发现其中一些结果可能是错的。他想知道，其中最多有多少个结果是正确的。

【输入格式】

第一行一个整数T，代表数据组数。接下来是T组数据。

每组数据的第一行是两个整数N,M，代表水箱被分成了多少个部分，以及结果的个数。

每组数据的第二行有N-1个整数h[1],h[2],...,h[N-1]，代表每一块隔板的高度。

接下来的M行，每一行形如"x y z"，如果第x个部分的y+0.5高度没有被淹没，则z=1，否则z=0。

【输出格式】

对每组数据，输出"Case #x: y"，其中x代表第几组数据（从1开始），y是最大可能的正确结果数。

【输入样例】

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

【输出样例】

Case #1: 3

Case #2: 1

【提示】

对于第一组数据，如果第1个结果正确，则第一部分的3.5高度有水。水将越过高度为3的隔板，因此第二部分水的高度至少和第一部分相等，这就与第2和第3个结果相矛盾。

1<=T<=10

1<=N<=10^5，1<=M<=2*10^5

1<=h[i]<=10^9

1<=y<=10^9

【来源】

HDU 5575 Discover Water Tank

2015ACM/ICPC亚洲区上海站-重现赛（感谢华东理工）