USACO Cow Lineup

USACO Cow Lineup

洛谷傳送門

JDOJ傳送門

Problem 1: Cow Lineup [Brian Dean and Daniel Dara, 2012]

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row. Each cow is

identified by an integer "breed ID" in the range 0...1,000,000,000; the

breed ID of the ith cow in the lineup is B(i). Multiple cows can share the

same breed ID.

FJ thinks that his line of cows will look much more impressive if there is

a large contiguous block of cows that all have the same breed ID. In order

to create such a block, FJ chooses up to K breed IDs and removes from his

lineup all the cows having those IDs. Please help FJ figure out

the length of the largest consecutive block of cows with the same breed ID

that he can create by doing this.

* Line 1: Two space-separated integers: N and K.

* Lines 2..1+N: Line i+1 contains the breed ID B(i).

* Line 1: The largest size of a contiguous block of cows with

identical breed IDs that FJ can create.

9 1 2 7 3 7 7 3 7 5 7

4

允許删K種，最後還必須連續，那麼想到滑動視窗。也就是，采用滑動視窗的模式周遊所有包含種類數小于等于K+1的區間們。為什麼是K+1呢，因為最多删除K種還剩一種。然後每次合法區間的最多種類來更新答案。

離散化開桶已經是套路的東西了，不需要說了。

然後我們思考如何快速找出每個合法區間的最多種類。

我們發現隻需要拿cow[a[r]]來更新答案就行了。因為每次右移較之上次移動都隻會有最右側的節點+。那麼每次更新也就是最右側節點。

代碼：