結果
| 問題 |
No.1526 Sum of Mex 2
|
| ユーザー |
 Rheo Tommy
|
| 提出日時 | 2021-04-29 22:19:39 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 267 ms / 3,000 ms |
| コード長 | 7,121 bytes |
| コンパイル時間 | 2,746 ms |
| コンパイル使用メモリ | 218,396 KB |
| 最終ジャッジ日時 | 2025-01-21 02:16:11 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 |
ソースコード
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int) n; i++)
using lint = long long;
const lint LINF = 1ll << 60;
class SegTreeBeats {
unsigned int n;
std::vector<lint> width, min[2], minc, max[2], maxc, sum, lazy;
void eval(int k) {
if (n - 1 <= k)return;
if (lazy[k]) {
update_node_add(2 * k + 1, lazy[k]);
update_node_add(2 * k + 2, lazy[k]);
lazy[k] = 0;
}
if (max[0][k] < max[0][2 * k + 1]) {
update_node_max(2 * k + 1, max[0][k]);
}
if (min[0][k] > min[0][2 * k + 1]) {
update_node_min(2 * k + 1, min[0][k]);
}
if (max[0][k] < max[0][2 * k + 2]) {
update_node_max(2 * k + 2, max[0][k]);
}
if (min[0][k] > min[0][2 * k + 2]) {
update_node_min(2 * k + 2, min[0][k]);
}
}
void combine(int k) {
sum[k] = sum[2 * k + 1] + sum[2 * k + 2];
if (min[0][2 * k + 1] < min[0][2 * k + 2]) {
min[0][k] = min[0][2 * k + 1];
minc[k] = minc[2 * k + 1];
min[1][k] = std::min(min[1][2 * k + 1], min[0][2 * k + 2]);
} else if (min[0][2 * k + 1] > min[0][2 * k + 2]) {
min[0][k] = min[0][2 * k + 2];
minc[k] = minc[2 * k + 2];
min[1][k] = std::min(min[0][2 * k + 1], min[1][2 * k + 2]);
} else {
min[0][k] = min[0][2 * k + 1];
minc[k] = minc[2 * k + 1] + minc[2 * k + 2];
min[1][k] = std::min(min[1][2 * k + 1], min[1][2 * k + 2]);
}
if (max[0][2 * k + 1] > max[0][2 * k + 2]) {
max[0][k] = max[0][2 * k + 1];
maxc[k] = maxc[2 * k + 1];
max[1][k] = std::max(max[1][2 * k + 1], max[0][2 * k + 2]);
} else if (max[0][2 * k + 1] < max[0][2 * k + 2]) {
max[0][k] = max[0][2 * k + 2];
maxc[k] = maxc[2 * k + 2];
max[1][k] = std::max(max[0][2 * k + 1], max[1][2 * k + 2]);
} else {
max[0][k] = max[0][2 * k + 1];
maxc[k] = maxc[2 * k + 1] + maxc[2 * k + 2];
max[1][k] = std::max(max[1][2 * k + 1], max[1][2 * k + 2]);
}
}
void update_node_max(int k, lint x) {
sum[k] += (x - max[0][k]) * maxc[k];
if (max[0][k] == min[0][k])min[0][k] = x;
else if (max[0][k] == min[1][k])min[1][k] = x;
max[0][k] = x;
}
void update_node_min(int k, lint x) {
sum[k] += (x - min[0][k]) * minc[k];
if (min[0][k] == max[0][k])max[0][k] = x;
else if (min[0][k] == max[1][k])max[1][k] = x;
min[0][k] = x;
}
void update_node_add(int k, lint x) {
min[0][k] += x;
if (min[1][k] != LINF)min[1][k] += x;
max[0][k] += x;
if (max[1][k] != -LINF)max[1][k] += x;
sum[k] += x * width[k];
lazy[k] += x;
}
public:
SegTreeBeats(unsigned int size, lint def = 0) {
*this = SegTreeBeats(std::vector<lint>(size, def));
}
SegTreeBeats(std::vector<lint> initvec) {
n = 1;
while (n < initvec.size())n *= 2;
width.resize(2 * n - 1);
min[0].resize(2 * n - 1);
min[1].resize(2 * n - 1, LINF);
minc.resize(2 * n - 1);
max[0].resize(2 * n - 1);
max[1].resize(2 * n - 1, -LINF);
maxc.resize(2 * n - 1);
sum.resize(2 * n - 1);
lazy.resize(2 * n - 1);
for (int i = n - 1; i < n - 1 + initvec.size(); i++) {
min[0][i] = max[0][i] = sum[i] = initvec[i - n + 1];
minc[i] = maxc[i] = 1;
}
for (int i = n - 2; i >= 0; i--) {
combine(i);
}
width[0] = n;
REP(i, 2 * n - 2) width[i] = width[(i - 1) / 2] / 2;
}
void update_chmin(int a, int b, lint x, int k = 0, int l = 0, int r = -1) {
if (r == -1)r = n;
if (b <= l || r <= a || max[0][k] <= x)return;
if (a <= l && r <= b && max[1][k] < x) {
update_node_max(k, x);
return;
}
eval(k);
update_chmin(a, b, x, 2 * k + 1, l, (l + r) / 2);
update_chmin(a, b, x, 2 * k + 2, (l + r) / 2, r);
combine(k);
}
void update_chmax(int a, int b, lint x, int k = 0, int l = 0, int r = -1) {
if (r == -1)r = n;
if (b <= l || r <= a || x <= min[0][k])return;
if (a <= l && r <= b && x < min[1][k]) {
update_node_min(k, x);
return;
}
eval(k);
update_chmax(a, b, x, 2 * k + 1, l, (l + r) / 2);
update_chmax(a, b, x, 2 * k + 2, (l + r) / 2, r);
combine(k);
}
void update_add(int a, int b, lint x, int k = 0, int l = 0, int r = -1) {
if (r == -1)r = n;
if (b <= l || r <= a)return;
if (a <= l && r <= b) {
update_node_add(k, x);
return;
}
eval(k);
update_add(a, b, x, 2 * k + 1, l, (l + r) / 2);
update_add(a, b, x, 2 * k + 2, (l + r) / 2, r);
combine(k);
}
void update(int a, int b, lint x) {
update_chmin(a, b, x);
update_chmax(a, b, x);
}
lint query_sum(int a, int b, int k = 0, int l = 0, int r = -1) {
if (r == -1)r = n;
if (b <= l || r <= a)return 0;
if (a <= l && r <= b)return sum[k];
eval(k);
lint vl = query_sum(a, b, 2 * k + 1, l, (l + r) / 2);
lint vr = query_sum(a, b, 2 * k + 2, (l + r) / 2, r);
return vl + vr;
}
lint query_min(int a, int b, int k = 0, int l = 0, int r = -1) {
if (r == -1)r = n;
if (b <= l || r <= a)return LINF;
if (a <= l && r <= b)return min[0][k];
eval(k);
lint vl = query_min(a, b, 2 * k + 1, l, (l + r) / 2);
lint vr = query_min(a, b, 2 * k + 2, (l + r) / 2, r);
return std::min(vl, vr);
}
lint query_max(int a, int b, int k = 0, int l = 0, int r = -1) {
if (r == -1)r = n;
if (b <= l || r <= a)return -LINF;
if (a <= l && r <= b)return max[0][k];
eval(k);
lint vl = query_max(a, b, 2 * k + 1, l, (l + r) / 2);
lint vr = query_max(a, b, 2 * k + 2, (l + r) / 2, r);
return std::max(vl, vr);
}
};
int main() {
lint n;
std::cin >> n;
std::vector<lint> v(n);
REP(i, n) std::cin >> v[i];
std::vector<std::vector<lint>> h(n + 1, std::vector<lint>(1, n));
h[0].push_back(0);
REP(i, n) {
h[v[i]].push_back(i);
}
REP(i, n + 1) {
std::sort(h[i].begin(), h[i].end());
std::reverse(h[i].begin(), h[i].end());
}
lint ans = 0;
SegTreeBeats st(n + 1);
REP(i, n + 1) {
lint p = h[i].back();
h[i].pop_back();
st.update_chmax(i, n + 2, p);
}
REP(i, n) {
ans += n * (n + 1) - st.query_sum(0, n + 2);
lint vi = v[i];
lint next = h[vi].back();
h[vi].pop_back();
st.update_chmax(vi, n + 2, next);
st.update_chmax(0, n + 2, i + 1);
}
std::cout << ans << std::endl;
}