LG 3587 [POI2015]POD

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转我们考虑两个断点(设为$l,r$)符合的条件:每种颜色的珠子只能出现在其中一条链中也就是若$[l,r]$中出现了某种颜色$[l,r]$也就包含了所有的这种颜色我们可以记录颜色出现的前缀和记录前$i$个位置每种颜色的出现次数,如果位置$i$是 颜色$a[i]$的最后一个位置, 就把颜色 $a[i]$ 的结果清零。这样若两个位置的前缀和相同,就是合法的可以通过 hash 来判断,记录所有 hash 值,排序后统计两个分割点 $l,r$ 要尽可能满足 $r−l$ 接近 $\frac n2$可以用类似双指针……