10121. 「一本通 4.2 例 3」与众不同

题意

定义完美序列:一段连续的序列满足序列中的数互不相同。 想知道区间 $[L,R]$ 之间最长的完美序列长度。

思路

设$las[x]$表示盈利$x$最近出现位置。 设$st[i]$表示以第$i$个数结尾的最长完美序列的起始位置。
$$st[i]=max(st[i-1],las[a[i]]+1)$$
设$f[i]$表示以第$i$个数结尾的最长完美序列的长度
$$f[i]=i-st[i]+1$$
由$st$的递推式可知,$st$的值是一个非递减的序列。 对于一个询问区间$[l_i,r_i]$,该区间内的$st$值可能会有两种情况:
  • 左边一部分的$st$值不在区间内,即$<l_i$
  • 右边一部分的$st$值不在区间内,即$\ge l_i$
由于$st$的值具有单调性,所以这个边界可以通过二分得到。设求出的边界为$mid$_i,可得:
$$st[l_i…mid_i-1]<l_i$$ $$st[mid_i…r_i]\ge l_i$$ 那么整个区间$[l_i,r_i]$的最长完美序列的长度可以分两部分来求。
  • 左边:很显然为$mid_i-l_i$
  • 右边:$MAX(m_i…r_i)$
所以右边的长度要使用ST表,即RMQ来求。 整个问题的时间复杂度:
$$O((M+N) \times logN)$$

评论

  1. none

    st[i]=max(st[i−1],las[a[i]+1]) 应为 st[i] = max(st[i – 1], las[a[i]] + 1)

    1月前
    2019-8-10 14:14:17
  2. yzx1798106406 博主

    fixed

    1月前
    2019-8-15 7:33:35

发送评论


				
上一篇
下一篇