| 记录编号 |
589000 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
雨滴之歌 |
最终得分 |
100 |
| 用户昵称 |
 yrtiop |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.907 s |
| 提交时间 |
2024-07-02 15:06:19 |
内存使用 |
51.65 MiB |
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
#define Tp template <typename T>
using i64 = long long;
using pii = std::pair<int, int>;
constexpr int maxn = 2e5 + 5, inf = 1e9 + 5;
int n, m, a[maxn], b[maxn];
Tp void chkmin(T& x, T y) { x = y < x ? y : x; return; }
Tp void chkmax(T& x, T y) { x = y > x ? y : x; return; }
struct ST1 {
int n, lg[maxn], st[20][maxn];
void init(int _n, int* a) {
n = _n;
for (int i = 1; i <= n; ++i) {
st[0][i] = a[i];
}
for (int i = 2; i <= n; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int k = 1; (1 << k) <= n; ++k) {
for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
st[k][i] = std::min(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
}
}
return;
}
int RMQ(int l, int r) {
if (l > r) std::swap(l, r);
int k = lg[r - l + 1];
return std::min(st[k][l], st[k][r - (1 << k) + 1]);
}
} mna, mnb;
struct ST2 {
int n, lg[maxn], st[20][maxn];
void init(int _n, int* a) {
n = _n;
for (int i = 1; i <= n; ++i) {
st[0][i] = a[i];
}
for (int i = 2; i <= n; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int k = 1; (1 << k) <= n; ++k) {
for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
st[k][i] = std::max(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
}
}
return;
}
int RMQ(int l, int r) {
if (l > r) std::swap(l, r);
int k = lg[r - l + 1];
return std::max(st[k][l], st[k][r - (1 << k) + 1]);
}
} mxa, mxb;
int S[maxn], T[maxn], c[maxn];
void add(int x, int y) {
if (!x) return;
for (; x <= n; x += x & -x) {
c[x] += y;
}
return;
}
int query(int x) {
int ans = 0;
for (; x > 0; x -= x & -x) {
ans += c[x];
}
return ans;
}
i64 solve(int* a, int* b, int l, int r) {
i64 ans = 0;
for (int i = r; i >= l; --i) {
ans += query(a[i]);
add(b[i], 1);
}
for (int i = l; i <= r; ++i) {
add(b[i], -1);
}
return ans;
}
int main() {
freopen("expansion.in", "r", stdin);
freopen("expansion.out", "w", stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin >> n >> m;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
for (int i = 1; i <= m; ++i) {
std::cin >> b[i];
}
mna.init(n, a);
mnb.init(m, b);
mxa.init(n, a);
mxb.init(m, b);
int mx = 0, dt = 0;
for (int i = n; i >= 1; --i) {
auto upd = [&]() {
S[i] = mx = 0;
return;
};
if (a[i] + mxb.RMQ(1, m) < 0) {
mx = S[i] = 0;
} else if (a[i] + mnb.RMQ(1, m) >= 0) {
chkmax(mx, i);
S[i] = mx;
++dt;
} else {
if (i == n || mxa.RMQ(i + 1, n) < a[i]) {
// upd();
continue;
}
int l = i + 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (mxa.RMQ(i + 1, mid) >= a[i]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (mxb.RMQ(1, m) + mna.RMQ(i, l) < 0) {
// upd();
continue;
}
int ql = 1, qr = m;
while (ql <= qr) {
int mid = (ql + qr) >> 1;
if (mxb.RMQ(1, mid) + mna.RMQ(i, l) >= 0) {
qr = mid - 1;
} else {
ql = mid + 1;
}
}
if (a[i] + mnb.RMQ(1, ql) >= 0) {
S[i] = S[l];
} else {
S[i] = 0;
}
}
}
int mn = n + 1;
std::fill(T + 1, T + 1 + n, n + 1);
for (int i = 1; i <= n; ++i) {
auto upd = [&]() {
T[i] = mn = n + 1;
return;
};
if (a[i] + mxb.RMQ(1, m) < 0) {
T[i] = mn = n + 1;
} else if (a[i] + mnb.RMQ(1, m) >= 0) {
chkmin(mn, i);
T[i] = mn;
} else {
if (i == 1 || mxa.RMQ(1, i - 1) < a[i]) {
// upd();
continue;
}
int l = 1, r = i - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (mxa.RMQ(mid, i - 1) >= a[i]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
l = r;
if (mxb.RMQ(1, m) + mna.RMQ(l, i) < 0) {
// upd();
continue;
}
int ql = 1, qr = m;
while (ql <= qr) {
int mid = (ql + qr) >> 1;
if (mxb.RMQ(mid, m) + mna.RMQ(l, i) >= 0) {
ql = mid + 1;
} else {
qr = mid - 1;
}
}
ql = qr;
if (a[i] + mnb.RMQ(ql, m) >= 0) {
T[i] = T[l];
} else {
T[i] = n + 1;
// upd();
}
}
}
i64 ans = solve(S, T, 1, n) + dt;
int lst = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] + mnb.RMQ(1, m) >= 0) {
ans -= solve(S, T, lst + 1, i - 1);
lst = i;
}
}
ans -= solve(S, T, lst + 1, n);
std::cout << ans << '\n';
return 0;
}