奇偶遊戲

題目連結

題意：有一個01串S，長度為n，一個人說出k個關于01串的回答，描述S[l~r] 中有奇數個1還是偶數個1。依次看，判斷他到第幾個問題都是可靠的回答。

思路：首先n很大要離散化，然後因為很容易想到如果S[l,r]為奇數，則S[1,r]為偶數,S[1,l-1]為奇數,或者S[1,r]為奇數,S[1,l-1]為偶數。如果S[l,r]為偶數，則

那兩個區間奇偶性相同。是以可以用擴充域，擴充每個[1,x]的奇數和偶數兩種情況，然後并查集。