[【codechefCHSEQ22】Chef and Favourite Sequence(并查集)

题目:http://hzwer.com/3419.html

题意:给你一个全是0的数列,有m种操作[Li,Ri],每次操作就将下标处于[Li,Ri]的元素取反。你可以选若干个操作来使这个数列最后变成别的样子,求最后的数列有多少种

分析:

容易知道如果每个操作都是不能被其他操作的组合替代,那么这个操作就对操作集合有贡献,不妨设有x个这样的操作,既然ans=操作集合的子集数,那么ans=2^x

那么问题的关键就是如何判断一个操作能否被其他操作取代

一个很巧的想法是对于每个操作[Li,Ri],将点Li、Ri连边,判断一个操作[Li,Ri]是否能被取代也就是判断Li、Ri是否连通,这个用并查集就行了

原文地址:https://www.cnblogs.com/wmrv587/p/4319456.html