【算法小白周赛1D】K阶恒星系

题目链接：https://www.starrycoding.com/contest/3/D

题目描述

牛马座 A 是个巨大的椭圆星系，具有 $n$ 个恒星。和太阳系一样，每个恒星周围都有许多行星。侥幸团队通过太空望远镜，观测出每个恒星系里行星的数量，其中第 $i$ 个恒星系里有 $p_i$ 个行星。若第 $i$ 个恒星系为侥幸团队定义的 $k$ 阶恒星系，则在正整数序列 $(p_1,p_2,… p_n)
$中，$ p_i$ 的左边和右边都至少有 $k$ 个元素的值小于 $p_i$

现在，侥幸团队请你统计出牛马座 A 中 $k$ 阶恒星系的数量。

输入格式

输入数据有 $2$ 行，第一行输入 $2$ 个正整数 $n, k$ ，分别表示恒星的数量和满足定义的 $k$ 值。

第二行：由 $n$ 个正整数构成的序列 $p_1,p_2,..., p_n$ 。

输出格式

一行一个正整数，表示牛马座 A 中 $k$ 阶恒星系的数量。

样例

样例输入#1

10 2
8 8 10 7 4 8 2 1 7 4

样例输出#1

解释#1

加粗的数字代表 $k$ 阶恒星系：8 8 10 7 4 8 2 1 7 4

样例输入#2

20 3
15 8 15 5 9 8 11 12 7 4 3 11 15 6 20 11 2 11 1 13

样例输出#2

数据范围

对于所有数据:

$1000 ≤ n ≤ 10^6$
$50 ≤ k ≤ 10^5$
$1 ≤ p_i ≤ n$

题解

题目大意：

有多少个数字前后都有 $m$ 个数字比这个数字小。

做法一：优先队列

我们先讨论 $p_i$ 左侧的情况，右侧按照同样的逻辑做处理就可以了：

注意到，我们只关心有没有至少 k 个元素，而不关心是哪些元素小于 $p_i$ 。因此，我们可以贪心地维护到当前位置时，最小的 $k$ 个元素。如果这 $k$ 个元素中最大的数字小于 $p_i$ ，则说明可以选出 $k$ 个来。否则不满足，并且 $p_i$ 可以替换掉原来的 $k$ 个元素中的最大数。

从上面可以看出，我们要动态地维护 $k$ 个元素，并且要频繁查询、删除最大值，和插入一个元素，用优先队列（大根堆）即可。

然后右侧同理。

时间复杂度 $O (n l o g n)$

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, k, p[N], ans;
bool f[N], g[N];
priority_queue<int> qf, qg;  // 维护到当前位置前最小的 k 个元素
int main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;for(int i = 1; i <= n; i++) {cin >> p[i];if(qf.size() < k) qf.push(p[i]), f[i] = false;else if(p[i] > qf.top()) f[i] = true;else qf.pop(), qf.push(p[i]), f[i] = false;}for(int i = n; i >= 1; i--) {if(qg.size() < k) qg.push(p[i]), g[i] = false;else if(p[i] > qg.top()) g[i] = true;else qg.pop(), qg.push(p[i]), g[i] = false;}for(int i = 1; i <= n; i++) {if(f[i] && g[i]) ans++;}cout << ans;return 0;
}

做法二：树状数组

观察到我们只需要找 $p_i$ 前后有多少个数字比自己大，很像一个求解逆序对问题，所以可以直接用树状数组

我们可以把所有的数字全部插入，设最大数为 $ma x n$ ，我们依次判断 $a_i$ 前面即 $query(a_i-1)$ 以及 $a_i$ 后面即 $query(maxn)-query(a_i)$ 是否含有 $k$ 个数字，插入比较简单，单点插入权值为1的数字即可。

AC Code

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target ("avx")
#pragma GCC optimize ("inline")#include <bits/stdc++.h>#define ios_close std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr)using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
#define Pi  acos(-1.0)template<typename T>
class BIT{
public:int sz;std::vector<T> t;BIT(){}BIT(int n){sz = n;t = std::vector<T>(sz + 1);}int lowbit(int x){return x & (-x);}void modfity(int x, T val){for(int i = x; i <= sz; i += lowbit(i)){t[i] += val;}       }T query(int x){T ans = 0;for(int i = x; i >= 1; i -= lowbit(i)){ans += t[i];}return ans;}
};void solve(){int n, k;std::cin >> n >> k;BIT<int> pre(n);std::vector<int> a(n + 1);std::vector<int> l(n + 1);std::vector<int> r(n + 1);for(int i = 1; i <= n; i ++ ){std::cin >> a[i];l[i] = pre.query(a[i] - 1);pre.modfity(a[i], 1);}BIT<int> suf(n);for(int i = n; i >= 1; i -- ){r[i] = suf.query(a[i] - 1);suf.modfity(a[i], 1);}int ans = 0;for(int i = 1; i <= n; i ++ ){//std::cout << l[i] << " " << r[i] << '\n';if(l[i] >= k && r[i] >= k){//std::cout << i << '\n';ans ++;}}std::cout << ans;
}int main(){
#if 0ios_close;
#endif#if 1freopen("kgalaxy.in", "r", stdin);freopen("kgalaxy.out", "w", stdout);
#endifint T = 1;
#if 0std::cin >> T;
#endif#if 0scanf("%d", &T);
#endifwhile(T -- ){solve();}return 0;
}