好久没写blog了顺便翻到半年前的黑历史
想写这篇blog,因为网上题解鬼话连篇我菜
然后突然看懂某篇题解,记录下来
题目链接
题意:
给出 n,c,k,和一个长度为n的数列
答案是最长所有数字出现 0 次或者 $\geq$ k次区间的长度
思路:
单看每个数字,会发现它们都有0个,1个或更多的合法区间
所有数字的合法区间之间交集就有可能是答案(这些交集可能不是连续的区间)
现在从左到右考虑每个数字,把它们当做右端点(枚举右端点)
那么就找到一个最左边(因为答案要最大)的合法左端点,然后这个区间长度和之前的答案取个max
(或者找不到)
对于当前第i个数(用x表示)来说
合法左端点是从 第1个数 到 第i个数右往左的第k个x
(网上好像还说 上一个x的下一个位置到i-1 这段,然而对于第i个数来说,左端点并不在这一段)
那么可以使用线段树,对某个点,如果它属于某个数合法左端点,就在这个点+1
当这个点加到了c时, 那么它和右端点就是答案的区间
这时候就可以更新答案
代码:
1 |
|
(或许我也鬼话连篇,只有我自己看懂我讲什么emm)