結果
| 問題 | No.3452 Divide Permutation |
| コンテスト | |
| ユーザー |
 lzm0107
|
| 提出日時 | 2026-02-25 17:50:14 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,714 bytes |
| 記録 | |
| コンパイル時間 | 3,113 ms |
| コンパイル使用メモリ | 346,784 KB |
| 実行使用メモリ | 56,884 KB |
| 最終ジャッジ日時 | 2026-02-25 17:51:04 |
| 合計ジャッジ時間 | 41,503 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 62 RE * 7 |
ソースコード
// Author: lzm0107
#include <bits/stdc++.h>
using namespace std;
constexpr int kMod = 998'244'353, kInf32 = 0x3f3f3f3f;
inline constexpr int Mod(int x) {
return x >= kMod ? x - kMod : x;
}
constexpr int kMaxN = 200'000;
int pw10[kMaxN + 10];
int n, p[kMaxN + 10], q[kMaxN + 10], prefix_hash[kMaxN + 10];
int ans[kMaxN + 10];
int sparse_table[2][__lg(kMaxN) + 2][kMaxN + 10];
struct Node {
bool complete;
int hash_val, len;
int frontmin, min_inversion;
Node operator+(Node rhs) const {
return {complete || rhs.complete,
(int)(((long long)hash_val * pw10[rhs.len] + rhs.hash_val) % kMod),
len + rhs.len, min(frontmin, rhs.frontmin),
min(min_inversion, rhs.min_inversion)};
}
};
Node d[(4 << __lg(kMaxN + 1)) + 10];
int pn;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
pw10[0] = 1;
for (int i = 1; i <= kMaxN; i++) {
pw10[i] = 10ll * pw10[i - 1] % kMod;
}
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i];
prefix_hash[i] = (10ll * prefix_hash[i - 1] + p[i]) % kMod;
q[p[i]] = i;
sparse_table[0][0][i] = sparse_table[1][0][i] = p[i];
}
for (int i = 1; 1 << i <= n; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
sparse_table[0][i][j] = min(sparse_table[0][i - 1][j], sparse_table[0][i - 1][j + (1 << i - 1)]);
sparse_table[1][i][j] = max(sparse_table[1][i - 1][j], sparse_table[1][i - 1][j + (1 << i - 1)]);
}
}
auto get_range_hash = [&](int l, int r) -> int {
return Mod(prefix_hash[r] + kMod - (long long)prefix_hash[l - 1] * pw10[r - l + 1] % kMod);
};
auto get_range_min = [&](int l, int r) -> int {
int tmp = 31 ^ __builtin_clz(r - l + 1);
return min(sparse_table[0][tmp][l], sparse_table[0][tmp][r - (1 << tmp) + 1]);
};
auto get_range_max = [&](int l, int r) -> int {
int tmp = 31 ^ __builtin_clz(r - l + 1);
return max(sparse_table[1][tmp][l], sparse_table[1][tmp][r - (1 << tmp) + 1]);
};
set<int> segment_start;
auto get_rep = [&](int x) -> int {
return *segment_start.rbegin() == x ? n : *segment_start.upper_bound(x) - 1;
};
pn = 2 << (31 ^ __builtin_clz(n + 1));
for (int i = 1; i < pn * 2; i++) {
d[i] = {false, 0, 0, kInf32, kInf32};
}
auto find_greater = [&](int x) -> int {
x += pn;
for (; x > 0; x >>= 1) {
if ((x & 1 ^ 1) && d[x ^ 1].complete) {
x ^= 1;
break;
}
}
if (x == 0) {
return -1;
}
while (x < pn) {
x <<= 1;
if (!d[x].complete) {
x ^= 1;
}
}
return x - pn;
};
auto find_less = [&](int x) -> int {
x += pn;
for (; x > 0; x >>= 1) {
if ((x & 1) && d[x ^ 1].complete) {
x ^= 1;
break;
}
}
if (x == 0) {
return -1;
}
while (x < pn) {
x <<= 1;
if (d[x ^ 1].complete) {
x ^= 1;
}
}
return x - pn;
};
auto query = [&](int l, int r) -> int {
int result = 0;
for (l += pn - 1, r += pn + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (l & 1 ^ 1) {
result += d[l ^ 1].len;
}
if (r & 1) {
result += d[r ^ 1].len;
}
}
return result;
};
auto update = [&](int x) -> void {
if (!segment_start.count(x)) {
d[p[x] + pn] = {false, 0, 0, kInf32, kInf32};
} else {
int rep = get_rep(x), tmp = get_range_min(x, rep), nex = find_greater(p[x]);
d[p[x] + pn] = {true, get_range_hash(x, rep), rep - x + 1, (tmp == p[x] ? kInf32 : tmp), (nex != -1 && get_range_max(x, rep) > nex ? p[x] : kInf32)};
}
for (int i = p[x] + pn >> 1; i > 0; i >>= 1) {
d[i] = d[i << 1] + d[i << 1 | 1];
}
};
segment_start.insert(1);
update(1);
auto flip_cut_state = [&](int x) -> void {
if (segment_start.count(x)) {
segment_start.erase(x);
} else {
segment_start.insert(x);
}
update(x);
if (segment_start.lower_bound(x) != segment_start.begin()) {
update(*prev(segment_start.lower_bound(x)));
}
int prv = find_less(p[x]);
if (prv != -1) {
update(q[prv]);
}
};
int cur_prefix = 0;
while ((int)segment_start.size() <= n) {
ans[segment_start.size()] = d[1].hash_val;
if (cur_prefix == n) {
for (int i = (int)segment_start.size() + 1; i <= n; i++) {
ans[i] = ans[i - 1];
}
break;
}
bool condition0 = (cur_prefix > 0 && q[cur_prefix] != n && p[q[cur_prefix] + 1] > cur_prefix + 1);
bool condition1 = (q[cur_prefix + 1] != 1 && p[q[cur_prefix + 1] - 1] > cur_prefix + 1);
if (condition0 && condition1) {
int val0, effect0;
int val1, effect1;
if (d[1].frontmin == kInf32) {
val0 = effect0 = kInf32;
} else {
val0 = d[1].frontmin;
int tmp = find_greater(val0);
effect0 = query(1, tmp - 1) + 1;
}
if (d[1].min_inversion == kInf32) {
val1 = effect1 = kInf32;
} else {
val1 = find_greater(d[1].min_inversion);
int pos = q[d[1].min_inversion];
int l = pos, r = n;
while (l + 1 < r) {
int mid = l + r >> 1;
if (get_range_max(pos, mid) > val1) {
r = mid;
} else {
l = mid;
}
}
effect1 = query(1, p[pos] - 1) + 1 + r - pos;
val1 = p[r];
}
if (effect0 == kInf32 && effect1 == kInf32) {
ans[segment_start.size() + 1] = d[1].hash_val;
} else {
if (effect0 < effect1) {
flip_cut_state(q[val0]);
} else {
flip_cut_state(q[val1]);
}
ans[segment_start.size()] = d[1].hash_val;
if (effect0 < effect1) {
flip_cut_state(q[val0]);
} else {
flip_cut_state(q[val1]);
}
}
}
if (condition0) {
flip_cut_state(q[cur_prefix] + 1);
}
if (condition1) {
flip_cut_state(q[cur_prefix + 1]);
}
++cur_prefix;
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
}