Parity题意描述样例输入：10{序列的长度L，1<=L<=1000000000}5{信息总数N,1<=N<=5000}12even{表示从第一位到第二位中含有偶数个1}34odd{表示从第三位到第四位中含有奇数个1}56even16even710odd原始的考虑——算法一两个区间之间的关系相交区间1区间2深入分析——算法二局部优化——算法三挖掘本质——算法四两种描述法的对应关系parity数组的所有下标构成了集合A＝{1，2，…，L}。这个集合根据元素i所对应的parity[i]的值是True还是False被划分成了两个等价类A1和A2，所有parity[i]=True的i归入A1中，所有parity[i]＝False的i则归入A2中。根据对应关系，p[i，j]的值是True还是False决定了parity[i-1]的值与parity[j]的值是否相同；实际上也就决定了i－1和j是否属于同一个等价类。这样，原来对每个区间[i，j]进行约束的条件就转化成了元素i-1，j是否属于同一个等价类的判断条件。定义集合same[i]表示已知与i在同一个等价类中的元素集合集合opp[i]表示已知与i不在同一个等价类中的元素集合根据已知条件，若有：parity[j]＝parity[i]，则j∈same[i]；parity[j]≠parity[i]，则j∈opp[i]；初始时，same[i]={i}，opp[i]=Ф。if与已知条件不矛盾thenifp[i,j]=truethenbegin合并(same[i],same[j])；合并(opp[i],opp[j])；endelsebegin合并(same[i],opp[j])；合并(same[j],opp[i])；endelse中止判断；具体实现时，我们可以应用并查集来完成所需的操作。理论上已经证明，如果利用按秩合并与路径压缩等技巧对程序进行充分优化，并查集这种数据结构的时间复杂度是O（N*α(N))的。其中，α(N)是单变量阿克曼函数的逆，它是一个增长速度比logN慢的多但又不是常数的函数。同时，我们已经将算法主体部分的时间复杂度降为O（N*α(N))的，查找部分再用O（logN）的二分查找就显得不合适了，因此我们考虑用更加高效的哈希表来实现查找。哈希表的查找时间是O（1）的，因此，算法中的查找时间是O（N）的。运行时间比较总结