树状数组
我们不难发现其实是维护一个堆,每次挑甜度最大的那个吃掉,并且要算距离
我们可以先排序,利用树状数组维护该距离,吃掉的甜甜圈删去,最后距离加上就是结果
C++ 代码
#include <bits/stdc++.h>javascript:void(0);
#define endl '\n'
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 2e6 + 10, INF = 0x3f3f3f3f;
int n, m;
int c[N];
PII a[N];
inline int lowbit(int x)
{
return x & -x;
}
inline void add(int x, int k)
{
for (int i = x; i <= n + m; i += lowbit(i)) c[i] += k;
}
inline int get(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += c[i];
return res;
}
inline void solve()
{
cin >> n >> m;
for (int i = n; i >= 1; i -- )
{
add(i, 1);
cin >> a[i].x;
a[i].y = i;
}
for (int i = n + 1; i <= n + m; i ++ )
{
add(i, 1);
cin >> a[i].x;
a[i].y = i;
}
sort(a + 1, a + 1 + n + m, [](PII a, PII b){
return a.x > b.x;
});
a[0].y = n;
long long res = 0;
for (int i = 1; i <= n + m; i ++ )
{
add(a[i].y, -1);
int cnt = get(a[i].y) > get(a[i - 1].y) ? (get(a[i].y) - get(a[i - 1].y)):(get(a[i - 1].y) - get(a[i].y));
res += cnt;
}
cout << res << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}