题解 P2471 【[SCOI2007]降雨量】

这里yea[i]表示第i个降雨量已知的年份，val[i]为第i个降雨量已知的年份的降雨量。 对于每一次询问，先求出从Y年开始往右查找最早能达到降雨量已知的年份编号u（之后的年份降雨量全部未知则为n+1）， 如已知降雨量的年份分别为45 47 49 56 58 79，那么50年和56年对应的编号都是4（56在序列中的位置为4）， 对于X年也求出往右查找最早能达到降雨量已知的年份编号v。由于年份是单调的，所以可用二分查找。 这样，求M年的降雨量是否已知，只需要先求出从M年开始往右查找最早能达到降雨量已知的年份编号s， 然后判断s != n + 1 && M == yea[s]。 分4种情况： 1、Y年和X年的降雨量都已知： 第一步，如果val[u] < val[v]，就说明不满足“X年的降雨量不超过Y年”这个条件，输出false并continue。 第二步，在v == u + 1的情况下，如果X == Y + 1就输出true（Y和X之间（不包括Y和X）没有整数）并continue，否则输出maybe并continue（Y和X之间存在降雨量未知的年份）。 第三步，查询[u + 1, v - 1]之间的最大值max（可用线段树或ST表维护），如果max >= val[v]，就说明不满足“对于任意 Y＜Z＜X，Z年的降雨量严格小于X年”这个条件，输出false并continue。 第四步，判断是否X - Y == v - u，如果为真就输出true（Y年和X年之间没有任何降雨量未知的年份），否则输出maybe（反之）。 2、Y年的降雨量未知，X年的降雨量已知： 第一步，如果u == v，输出maybe（Y年和X年之间年份的降雨量全部未知）并continue。 第二步，查询[u, v - 1]之间的最大值max，如果max >= val[v]，就说明不满足“对于任意Y＜Z＜X，Z年的降雨量严格小于X年”这个条件，输出false，否则输出maybe（Y年和X年的降雨量只要有一个未知就不能确定这句话是否一定为真）。 3、Y年的降雨量已知，X年的降雨量未知： 第一步，如果v == u + 1，输出maybe（Y年和X年的降雨量只要有一个未知就不能确定这句话是否一定为真）并continue。 第二步，查询[u + 1, v - 1]之间的最大值max，如果val[u] <= max，就说明X年的降雨量M不管为多少都无法同时满足M > max和 M <= val[u]，输出false，否则输出maybe（Y年和X年的降雨量只要有一个未知就不能确定这句话是否一定为真）。 4、Y年和X年的降雨量都未知：输出maybe（Y年和X年的降雨量只要有一个未知就不能确定这句话是否一定为真）。