結果
| 問題 |
No.3122 Median of Medians of Division
|
| ユーザー |
 keymoon
|
| 提出日時 | 2025-04-19 07:44:42 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,306 bytes |
| コンパイル時間 | 4,267 ms |
| コンパイル使用メモリ | 312,744 KB |
| 実行使用メモリ | 139,768 KB |
| 最終ジャッジ日時 | 2025-04-19 07:44:58 |
| 合計ジャッジ時間 | 13,044 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 39 |
ソースコード
// written by ChatGPT o4-mini-high (really sorry)
#include <bits/stdc++.h>
using namespace std;
/* ---------- 二段 Fenwick ---------- */
struct BIT2 {
int n;
vector<vector<int>> coord; // 各ノードに載る値(圧縮済)
vector<vector<int>> bit; // 内側 Fenwick
BIT2(int N = 0) : n(N), coord(N + 1) {}
// 構築：add_coord で全候補値を登録したあと build()
void add_coord(int idx, int val) {
for (int i = idx; i <= n; i += i & -i) coord[i].push_back(val);
}
void build() {
for (int i = 1; i <= n; ++i) {
auto &v = coord[i];
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
bit.emplace_back(v.size() + 1, 0); // 1-indexed
}
}
/* 内側 Fenwick */
static void fen_add(vector<int>& f, int idx, int delta) {
for (int i = idx; i < (int)f.size(); i += i & -i) f[i] += delta;
}
static int fen_sum(const vector<int>& f, int idx) {
int s = 0;
for (int i = idx; i > 0; i -= i & -i) s += f[i];
return s;
}
int pos_in(int i, int val) const { // < val の個数 ⇒ lower_bound
return lower_bound(coord[i].begin(), coord[i].end(), val) - coord[i].begin();
}
/* 1点加算 / 区間個数(< val) */
void add(int idx, int val, int delta) {
for (int i = idx; i <= n; i += i & -i) {
int p = lower_bound(coord[i].begin(), coord[i].end(), val) - coord[i].begin() + 1;
fen_add(bit[i - 1], p, delta); // bit は 0-origin vector
}
}
int prefix_less(int idx, int val) const { // [1,idx] で < val
int res = 0;
for (int i = idx; i > 0; i -= i & -i) {
int p = pos_in(i, val);
res += fen_sum(bit[i - 1], p);
}
return res;
}
int range_less(int l, int r, int val) const { // [l,r]
if (l > r) return 0;
return prefix_less(r, val) - prefix_less(l - 1, val);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q; cin >> N >> Q;
vector<long long> A(N + 2); // 1-indexed, 番兵付き
for (int i = 1; i <= N; ++i) cin >> A[i];
/* ---- 全値収集 ---- */
vector<vector<long long>> candA(N + 2); // 位置ごとの候補値
for (int i = 1; i <= N; ++i) candA[i].push_back(A[i]);
vector<tuple<int,int,long long>> queries; // (type, p1, p2/x)
for (int t = 0; t < Q; ++t) {
int tp; cin >> tp;
if (tp == 1) {
int i; long long x; cin >> i >> x;
queries.emplace_back(tp, i, x);
candA[i].push_back(x);
} else {
int l, r; cin >> l >> r;
queries.emplace_back(tp, l, r);
}
}
/* ---- 座標圧縮 ---- */
vector<long long> all;
for (int i = 1; i <= N; ++i) {
for (auto v : candA[i]) all.push_back(v);
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
auto idx = [&](long long x) { return int(lower_bound(all.begin(), all.end(), x) - all.begin()); };
/* ---- BIT 構築：A用 ---- */
BIT2 bitA(N);
for (int i = 1; i <= N; ++i) {
for (auto v : candA[i]) bitA.add_coord(i, idx(v));
}
bitA.build();
/* ---- 隣接 min 配列 D ---- */
int M = max(1, N - 1);
vector<vector<long long>> candD(M + 2);
auto addDcand = [&](int dIdx, long long v) {
if (dIdx < 1 || dIdx > M) return;
candD[dIdx].push_back(v);
};
for (int i = 1; i <= M; ++i) {
long long v = min(A[i], A[i + 1]);
addDcand(i, v);
}
for (auto [tp,p1,p2] : queries) if (tp == 1) {
int i = p1; long long x = p2;
addDcand(i - 1, min(x, A[i - 1]));
addDcand(i, min(x, A[i + 1]));
}
BIT2 bitD(M);
for (int i = 1; i <= M; ++i)
for (auto v : candD[i]) bitD.add_coord(i, idx(v));
bitD.build();
/* ---- 初期値登録 ---- */
for (int i = 1; i <= N; ++i) bitA.add(i, idx(A[i]), +1);
vector<int> Dval(M + 2, -1);
for (int i = 1; i <= M; ++i) {
Dval[i] = idx(min(A[i], A[i + 1]));
bitD.add(i, Dval[i], +1);
}
/* ---- 2 種クエリ処理 ---- */
auto works = [&](int l, int r, int id) -> bool {
long long vRaw = all[id];
int len = r - l + 1;
int lowCnt = bitA.range_less(l, r, id); // A_i < v
int high = len - lowCnt;
if (high == 0) return false;
int pairCnt = max(0, r - l);
int lowPair = bitD.range_less(l, r - 1, id); // D_i < v
int adjHigh = pairCnt - lowPair; // both ≥ v
int groups = high - adjHigh;
int startLow = (A[l] < vRaw);
int endLow = (A[r] < vRaw);
long long lowBlocks = groups - 1 + startLow + endLow;
return high > lowBlocks;
};
ostringstream out;
for (auto [tp,p1,p2] : queries) {
if (tp == 1) { /* 更新 */
int i = p1; long long x = p2;
if (A[i] == x) continue;
/* A の BIT 更新 */
bitA.add(i, idx(A[i]), -1);
bitA.add(i, idx(x), +1);
/* 隣接 D の更新 */
auto updD = [&](int dIdx) {
if (dIdx < 1 || dIdx > M) return;
bitD.add(dIdx, Dval[dIdx], -1);
long long newRaw = min(A[dIdx], A[dIdx+1]);
if (dIdx == i - 1) newRaw = min(A[dIdx], x);
if (dIdx == i) newRaw = min(x, A[dIdx+1]);
Dval[dIdx] = idx(newRaw);
bitD.add(dIdx, Dval[dIdx], +1);
};
updD(i - 1);
updD(i);
A[i] = x;
} else { /* 質問 */
int l = p1, r = (int)p2;
/* 長さ 1 はそのまま */
if (l == r) { out << A[l] << '\n'; continue; }
int lo = 0, hi = (int)all.size() - 1, ans = all[0];
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (works(l, r, mid)) { ans = all[mid]; lo = mid + 1; }
else hi = mid - 1;
}
out << ans << '\n';
}
}
cout << out.str();
return 0;
}