成功的秘诀,在于克服自己看题解的冲动……【笑哭】。自己A掉这题还是灰常开心的~
以及爱死 two – pointer ! two – pointer 大法是真的好哇……这个题目有上一题的经验:求第\(K\) 大 –> 二分第 \(K\) 大的值 –> 检验当前二分的值排名是第几。而这样之所以可以解决问题在于:直接求第 \(K\) 并不好求,而检验一个值的排名却相对容易。所以我们现在的问题就转化为了如何计算出区间的值 \(>= mid\) 的区间的个数?
做题之前先找规律 & 性质。这里我们注意到:如果我们固定一个右端点,那么区间的值是随着区间的长度单调不减的。……好像和 two – pointer有点像?如果当前的 \(l –> r\) 区间满足区间的值 \(>= mid\), 则 \(1 — > l – 1\) 也同样是满足的。这样,只需要在找到第一个 \(l, r\)之后不断右移左端点就可以了。计算区间众数可以采取和莫队一样的处理方法。
以及……要开 long long??? 我也不知道发生了什么……
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000
#define int long long
int n, tot, K, now, a[maxn], b[maxn];
int ans, num[maxn], cnt[maxn];
map <int, int> Map;int read()
{
int x = , k = ;
char c; c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
}void Add(int x)
{
num[cnt[a[x]]] --; cnt[a[x]] ++; num[cnt[a[x]]] ++;
if(cnt[a[x]] > now) now = cnt[a[x]];
}void Minus(int x)
{
if(now == cnt[a[x]] && num[cnt[a[x]]] <= ) now --;
num[cnt[a[x]]] --; cnt[a[x]] --; num[cnt[a[x]]] ++;
}bool Check(int mid)
{
memset(num, , sizeof(num));
memset(cnt, , sizeof(cnt));
now = ; int ans = ;
for(int l = , r = ; r <= n; r ++)
{
if(now < mid) Add(r);
while(l <= r && now >= mid) Minus(l), l ++;
ans += l - ;
}
if(ans >= K) return ;
else return ;
}signed main()
{
n = read(), K = read();
for(int i = ; i <= n; i ++) a[i] = b[i] = read();
sort(b + , b + + n); b[] = -;
for(int i = ; i <= n; i ++)
if(b[i] != b[i - ]) Map[b[i]] = ++ tot;
for(int i = ; i <= n; i ++) a[i] = Map[a[i]];
int l = , r = n;
while(l <= r)
{
int mid = (l + r) >> ;
if(Check(mid)) ans = mid, l = mid + ;
else r = mid - ;
}
printf("%lld\n", ans);
return ;
}