#108. 「Parity Game」 奇偶游戏

「Parity Game」 奇偶游戏

小A和小B在玩一个游戏。

首先,小A写了一个由0和1组成的序列S,长度为N。

然后,小B向小A提出了M个问题。

在每个问题中,小B指定两个数 l 和 r,小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如,小A曾经回答过 S[1~3] 中有奇数个1, S[4~6] 中有偶数个1,现在又回答 S[1~6] 中有偶数个1,显然这是自相矛盾的。

请你帮助小B检查这M个答案,并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k,使得01序列S满足第1~k个回答,但不满足第1~k+1个回答。

输入格式

第一行包含一个整数N,表示01序列长度。

第二行包含一个整数M,表示问题数量。

接下来M行,每行包含一组问答:两个整数l和r,以及回答“even”或“odd”,用以描述S[l~r] 中有偶数个1还是奇数个1。

输出格式

输出一个整数k,表示01序列满足第1~k个回答,但不满足第1~k+1个回答,如果01序列满足所有回答,则输出问题总数量。

数据范围

N109,M10000N \le 10^9 , M \le 10000

输入样例:

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

输出样例:

3

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解