问题 5267 --奇偶--并查集训练T3

5267: 奇偶--并查集训练T3

时间限制: 1 Sec  内存限制: 128 MB
提交: 50  解决: 8
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][384kb]

题目描述

T3.奇偶(Parity.pas)

【问题描述】

AB在玩一个游戏:他写一个由01组成的序列。

A选其中的一段(比如第3位到第5位),问他这段里面有奇数个1还是偶数个1

B回答你的问题,然后A继续问。

B有可能在撒谎。A要检查B的答案,指出在B的第几个回答一定有问题。

有问题的意思就是存在一个01序列满足这个回答前的所有回答,而且不存在序列

满足这个回答前的所有回答及这个回答。

【输入格式】

1行一个整数,是这个01序列的长度(<=1000000000)

2行一个整数,是问题和答案的个数。

3行开始是问题和答案,

每行先有两个整数,表示你询问的段的开始位置和结束位置。

然后是B的回答。odd表示有奇数个1even表示有偶数个1

【输出格式】

输出一行,一个数X,表示存在一个01序列满足第1到第X个回答,

但是不存在序列满足第1到第X+1个回答。如果所有回答都没问题,你就输出

所有回答的个数。

【输入样例】

10

5

1 2 even

3 4 odd

5 6 even

1 6 even

7 10 odd

【输出样例】

3


 

输入

输出

提示

来源

[提交][状态]