较高端的并查集.docVIP

Parity game [问题描述] 你和你的朋友玩以下的游戏：你的朋友写下一个由0和1组成的字符串，你从中选择连续的子串（例如从第3个到第5个连续的3个数字），然后问他这个子串中1的个数是奇数还是偶数，你的朋友回答了，然后你再继续问类似的问题。你估计你朋友的回答中有一些是错误的，你想证明他的错误，所以你决定编写一个程序来帮你解决这个问题。这个程序会根据你的问题以及他的回答来判断他是否错了，你程序的目标是找到第1个可能的错误回答，也就是说存在一个数字串满足前面所有的问题，但对于当前的问题不满足而且没有一个数字串满足。 ? [输入] 第1行：一个数字，告诉你该数字串的个数（=1000000）； 第2行：一个数字，告诉你总共提了多少问题（=5000）； 剩下的各行，每行是一个问题和对应的回答，每行共有3部分组成，每部分之间有一个空格隔开，第1部分是一个整数表示子串的开始位置，第2部分也是一个整数表示子串的结束位置，第3部分是一个单词（even表示子串中1的个数是偶数；odd表示子串中1的个数是奇数）。 ? [输出] 只有1个整数X，该整数表示存在一个01的数串满足前X个奇偶条件，但不满足第X+1个奇偶条件。若存在一个01串满足所有的条件，则X就是所有问题的个数。 ? [样例输入与输出] 输入： 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 输出： 3 ? 输入： 10 5 1 2 even 1 4 even 2 4 odd 1 10 even 3 10 even 输出： 5 奇偶性：设奇数为true, 偶数为false。问答(l, r, p)就是得到序列上l到r之间的1的个数的奇偶性为p。 ?????? 一次处理r-l+1个数不方便，可以转化为部分和的形式。记Sum[x] 为从序列中的第1个数到第x个数中1的个数。则问答(l, r, p)，转化为odd(Sum[r] - Sum[l-1]) = p。若也把Sum看成是奇偶性表示则上式为Sum[r] xor Sum[l-1]=p，这样就可以得到Sum[l-1]与Sum[r]的关系。若出现了错误就是与之前的问答以及它们推出的结论有矛盾。为了表示前面问答与推出的结论，可以采用并查集实现。 ?????? 下面改造并查集，每个结点指向父亲的指针F[x]上，再增加一个表示与父亲奇偶性差异的布尔变量P[x]（若与父亲奇偶性等价则P[x]=false, 否则P[x]=true）。某个结点x到根o的路径上的所有P[i]，xor起来就是x相对于根o的奇偶性差异，简记为P[x, o]。易知，P[x]也是可以路径压缩的。 ?????? 对于一个询问(l, r, p)：若l-1与r是属于同一个集合，则检查l-1与r相对于根o的奇偶性差异P[l -1, o]与P[r, o]。看这两个差异值的差异是不是就是p，即P[l-1, o] xor P[r, o]是不是等于p，不是则矛盾。若l-1与r是不属于同一个集合，则将l-1与r所在树的根节点合并起来，这两个根结点间奇偶性差异为P[l-1,o] xor P[r, o] xor p。 ?????? 由于序列的大小很大，且不必都要处理到，而N却比较小，可以用Hash表来记录这些离散点。 Rochambeau Time limit: 5 Seconds?? Memory limit: 32768K?? N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don\t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gestur