Submission #63853706

---

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].from(*@a[i+i,2])
		}
		@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.concat @a[i]
		else
			j = i+i
			m = l+(r-l)/2
			unless @b[i].nop?
				@a[j].apply @b[i]
				@b[j].merge @b[i]
				@a[j+1].apply @b[i]
				@b[j+1].merge @b[i]
				@b[i].nop!
			end
			get(j,l,m,ql,qr,v) if ql<m
			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].apply v
			@b[i].merge v
		else
			j = i+i
			m = l+(r-l)/2
			unless @b[i].nop?
				@a[j].apply @b[i]
				@b[j].merge @b[i]
				@a[j+1].apply @b[i]
				@b[j+1].merge @b[i]
				@b[i].nop!
			end
			set(j,l,m,ql,qr,v) if ql<m
			set(j+1,m,r,ql,qr,v) if m<qr
			@a[i].from(*@a[j,2])
		end
	end
end

P = 998244353

class Seg
	def initialize x
		@x = x
	end
	attr_reader :x

	def from l,r
		@x = [l.x,r.x].max
		self
	end
	def concat r
		@x = [@x,r.x].max
		self
	end
	def apply op
		@x += op.v
		self
	end
end
class Op
	def initialize v
		@v = v
	end
	attr_reader :v

	def nop?
		@v==0
	end

	def nop!
		@v = 0
		self
	end
	def merge other
		@v += other.v
		self
	end
end

N,*A = $<.read.split.map(&:to_i)
I = Array.new(N+1){[]}
A.each_with_index{|a,i|
	I[a]<<i
}
この区間で切ったら種類数が減らない = ST.new Array.new(N){ Seg.new 0 },Seg.new(0),Op.new(0)
I.each{|is|
	この区間で切ったら種類数が減らない[is[0],is[-1]-1] = Op.new(1) if 1<is.size
}
L,R = {},A.tally
L.default = R.default = 0
l,r = 0,R.size
p A[0,N-2].map.with_index{|a,i|
	l += 1 if 1==L[a] += 1
	r -= 1 if 0==R[a] -= 1
	I[a].shift
	この区間で切ったら種類数が減らない[i,I[a][0]-1] = Op.new(-1) if I[a][0]
	l+r+この区間で切ったら種類数が減らない[i+1,N-2].x
}.max

Submission Info

Judge Result