Submission #63857023

---

Source Code Expand

class ST
	def initialize a,e,op
		@l = 1<<(a.size-1).bit_length
		@a = Array.new(@l){ e.dup }
		@a.concat a
		@a.concat [e]*(@l-a.size)
		(@l-1).downto(1){|i|
			@a[i] = @a[i+i,2].max
		}
		@b = @a.map{ op.dup }
		@e = e
	end

	def [] l,r=l
		get 1,0,@l,l,r+1,@e.dup if l<=r
	end

	def []= l,r=l,v
		set 1,0,@l,l,r+1,v if l<=r
	end

private
	def get i,l,r,ql,qr,v
		if qr<=l || r<=ql
		elsif ql<=l && r<=qr
			v = [v,@a[i]].max
		else
			j = i+i
			m = l+(r-l)/2
			unless @b[i]==0
				@a[j] += @b[i]
				@b[j] += @b[i]
				@a[j+1] += @b[i]
				@b[j+1] += @b[i]
				@b[i] = 0
			end
			v = get(j,l,m,ql,qr,v) if ql<m
			v = get(j+1,m,r,ql,qr,v) if m<qr
		end
		return v
	end

	def set i,l,r,ql,qr,v
		if qr<=l || r<=ql
		elsif ql<=l && r<=qr
			@a[i] += v
			@b[i] += v
		else
			j = i+i
			m = l+(r-l)/2
			unless @b[i]==0
				@a[j] += @b[i]
				@b[j] += @b[i]
				@a[j+1] += @b[i]
				@b[j+1] += @b[i]
				@b[i] = 0
			end
			set(j,l,m,ql,qr,v) if ql<m
			set(j+1,m,r,ql,qr,v) if m<qr
			@a[i] = @a[j,2].max
		end
	end
end

N,*A = $<.read.split.map(&:to_i)

L,R = Hash.new(0),A.tally
I = Array.new(N+1){[]}
A.each_with_index{|a,i|
	I[a]<<i
}
D = [0]*N
I.each{|is|
	if is[1]
		D[is[0]] += 1
		D[is[-1]] -= 1
	end
}
b = 0
B = D.map{ b += _1 }
この区間で切ったら種類数が減らない = ST.new B,0,0
p A[0,N-2].map{|a|
	L[a] += 1
	R.delete a if 0==R[a] -= 1
	i = I[a].shift
	この区間で切ったら種類数が減らない[i,I[a][0]-1] = -1 if I[a][0]
	L.size+R.size+この区間で切ったら種類数が減らない[i+1,N-2]
}.max

Submission Info

Judge Result