3952. Fair Photography

Description

数轴上某些位置有一个种类a，选一个最大的区间使得里面每个种类a出现的次数都相等而且种类个数》=k
n<=100000,2《=k<=8,种类数《8

Idea

其实关于区间问题，都是各种套路
这里我们可以选定状态s，规定我们选哪几个种类，这样符合的位置就会得出一个又一个互不相交的区间
设得出一个区间[l,r]
我们顺着扫一遍，记录当前位置到l里各种牛的个数，在求出相对状态（即所有在状态s的牛的个数都减去他们当中最小的哪个）（4，6,5）变成（0,2,1）,如果之前出现过相对状态为（0,2,1），则说明存在合法区间
至于找相对状态相同的，可以用双哈希
时间复杂度（2^8*n*8）