Readme

2963.Count-the-Number-of-Good-Partitions

根据题意，相同的数字必须在同一个subarray里。所以对于每一个数字，我们找到它在数组中最左边出现的位置L，和最右边出现的位置R，那么[L,R]这个区间必须在同一个subarray里。

此外，如果有两个区间（对应数字a和b）有任何程度的重合，那么这两个区间必然也在同一个subarray里，才能保证a和b不出现在其他subarray里。

由此根据所得到的若干个区间，我们就可以用差分数组（即扫描线）来进行合并，求得数组里有多少个互不相同的subarray，假设为n。那么这n个subarray必然是满足条件的最多分割。此外，这些subarray的任意合并也必然是满足条件的一种分割。根据插板法的道理，这样的分割数目有2^(n-1)个。