场G了????!!!
我已严肃会线段树!
题目本质上是让我们求一个∑∑mex(al.....ar)\sum{\sum{mex(a_l.....a_r)}}∑∑mex(al .....ar )这么个东西
遇到这种双层循环+求区间的操作,第一想法是固定lll,计算rrr的贡献。
考虑从lll到l+1l+1l+1所产生的影响,我们失去了ala_lal ,而下一个ala_lal 我们记为nxtalnxt_{a_l}nxtal (若没有就是n+1n+1n+1),我们可能影响的区间是[l+1,nxtal−1][l+1,nxt_{a_l}-1][l+1,nxtal −1]!
考虑情况:
1.若这个区间的最大mexmexmex值都比ala_lal 还小,显然对这段区间无影响。
2.反之,相当于做一个区间覆盖,用ala_lal 更新这个区间,所以用线段树维护!
所以就做完了,时间复杂度O(nlogn)O(n \log n)O(nlogn)