CFR 486 E. LIS of Sequence ( DP, Fenwick Tree )

Problem - E - Codeforces

題意：
給一個數列，對每一個值輸出：
1 if 它不屬於任何一個 LIS
2 if 它屬於某個 LIS，但沒有它也存在相同長度的 LIS
3 if 拔掉它的話 LIS 長度會改變

制約：
N ≤ 1e5
A ≤ 1e5

解法：
用 dp 跟 BIT 的要領求出
st_len[ i ]: 以位置 i 為首的 LIS 的最大長度
ed_len[ i ]: 以位置 i 為尾的 LIS 的最大長度
令原數列的 LIS 長度為 max_len，並計算：
st_cnt_len[ i ]: 位置 x 屬於任意一個最大的 LIS 中的元素之一，i = st_len[ x ] 的數量
若且唯若位置 i 屬於任意一個最大的 LIS 中的元素之一且 st_cnt_len[ st_len[ i ] ] == 1，它屬於 3。

時間 / 空間複雜度：
O( N lg A ) / O( N + A )

N = int( input() )
A = list( map( int, input().split() ) )

maxa = max( A )

def upd( ftree, x, v ):
  while x <= maxa:
    ftree[ x ] = max( ftree[ x ], v )
    x += x & -x

def qry( ftree, x ):
  res = 0
  while x:
    res = max( res, ftree[ x ] )
    x -= x & -x
  return res

st_len = [ 0 for i in range( N ) ]
ftree = [ 0 for i in range( maxa + 1 ) ]
for i in range( N - 1, -1, -1 ):
  st_len[ i ] = qry( ftree, maxa + 1 - A[ i ] - 1 ) + 1
  upd( ftree, maxa + 1 - A[ i ], st_len[ i ] )

ed_len = [ 0 for i in range( N ) ]
ftree = [ 0 for i in range( maxa + 1 ) ]
for i in range( N ):
  ed_len[ i ] = qry( ftree, A[ i ] - 1 ) + 1
  upd( ftree, A[ i ], ed_len[ i ] )

max_len = max( st_len )
st_cnt_len = [ 0 for i in range( N + 1 ) ]
for i in range( N ):
  if ed_len[ i ] + st_len[ i ] - 1 == max_len:
    st_cnt_len[ st_len[ i ] ] += 1

for i in range( N ):
  if ed_len[ i ] + st_len[ i ] - 1 != max_len:
    print( 1, end = "" )
  elif st_cnt_len[ st_len[ i ] ] > 1:
    print( 2, end = "" )
  else:
    print( 3, end = "" )
print()