将数据离散化后,就是经典的判断区间和是否正确的带权并查集。
题意
现在告诉你很多段区间的和的奇偶情况, 问到哪一句就不正确了。
思路
由于区间长度很大,但是区间段数很少,所以需要先离散化一下,然后维护每个端点到他所在根节点的权值,也就是到根节点所在端点的奇偶情况,当询问L,R时, 我们就判断val[L - 1] - val[R] 的奇偶情况是不是与输入的相符即可。
注意输入字符串用char,不要用string,不是一般的超时。
1 |
|
云腾致雨,露结为霜
将数据离散化后,就是经典的判断区间和是否正确的带权并查集。
现在告诉你很多段区间的和的奇偶情况, 问到哪一句就不正确了。
由于区间长度很大,但是区间段数很少,所以需要先离散化一下,然后维护每个端点到他所在根节点的权值,也就是到根节点所在端点的奇偶情况,当询问L,R时, 我们就判断val[L - 1] - val[R] 的奇偶情况是不是与输入的相符即可。
注意输入字符串用char,不要用string,不是一般的超时。
1 | #include <set> |