LG UVA1608 不无聊的序列 Non-boring sequences

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转我们先预处理出$L_i,R_i$分别表示与$a_i$相同的数出现在$i$左边和右边的位置我们可以使用分治来判断一个区间是否合法我们设当前区间为$[l,r]$从两边一起找假设枚举到位置$i$若$L_i<l$且$R_i>r$,那么左端点在$[l,i]$,右端点在$[i,r]$的区间都是"non-boring"这时我们只需要判断区间$[l,i-1]$和$[i+1,r]$是否合法就可以了复杂度可以降至$\Theta(n \log n)$……