結果
| 問題 |
No.3122 Median of Medians of Division
|
| ユーザー |
 shibh308
|
| 提出日時 | 2025-04-20 06:31:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,779 bytes |
| コンパイル時間 | 3,420 ms |
| コンパイル使用メモリ | 254,392 KB |
| 実行使用メモリ | 146,200 KB |
| 最終ジャッジ日時 | 2025-04-20 06:31:45 |
| 合計ジャッジ時間 | 11,559 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 39 |
ソースコード
// # pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 二次元 Fenwick Tree:
// - x ∈ [0..n-1], y は各 x で事前に登録された値集合から選択
struct BIT2D {
int n;
vector<vector<int>> ys, t;
BIT2D(int _n = 0) : n(_n), ys(n+1) {}
// 構築フェーズ：(x,y) が将来更新で使われうることを登録
void fake_add(int x, int y) {
for(int i = x+1; i <= n; i += i & -i)
ys[i].push_back(y);
}
// fake_add 後に一度だけ呼び出し、内部の BIT 配列を初期化
void init() {
t.resize(n+1);
for(int i = 1; i <= n; i++) {
auto &v = ys[i];
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
t[i].assign(v.size()+1, 0);
}
}
// BIT における (x,y) への加算
void update(int x, int y, int v) {
for(int i = x+1; i <= n; i += i & -i) {
int k = int(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin()) + 1;
for(int j = k; j < (int)t[i].size(); j += j & -j)
t[i][j] += v;
}
}
// [0..x]×[0..y] の累積和
int query_prefix(int x, int y) const {
int res = 0;
for(int i = x+1; i > 0; i -= i & -i) {
int k = int(upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
for(int j = k; j > 0; j -= j & -j)
res += t[i][j];
}
return res;
}
// [xl..xr]×[yl..yr] の和
int query(int xl, int xr, int yl, int yr) const {
if(xl > xr || yl > yr) return 0;
return query_prefix(xr, yr)
- query_prefix(xl-1, yr)
- query_prefix(xr, yl-1)
+ query_prefix(xl-1, yl-1);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<ll> A(N);
for(int i = 0; i < N; i++) cin >> A[i];
struct Query { int type; int i, l, r; ll x; };
vector<Query> qs(Q);
// 1) 先読み：各位置 i の A 候補値を集める
vector<vector<ll>> posA_val(N);
for(int i = 0; i < N; i++)
posA_val[i].push_back(A[i]);
for(int qi = 0; qi < Q; qi++){
cin >> qs[qi].type;
if(qs[qi].type == 1){
cin >> qs[qi].i >> qs[qi].x;
--qs[qi].i;
posA_val[qs[qi].i].push_back(qs[qi].x);
} else {
cin >> qs[qi].l >> qs[qi].r;
--qs[qi].l; --qs[qi].r;
}
}
// 2) 座標圧縮
vector<ll> allA;
allA.reserve(N + Q);
for(int i = 0; i < N; i++){
auto &v = posA_val[i];
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(ll x : v) allA.push_back(x);
}
sort(allA.begin(), allA.end());
allA.erase(unique(allA.begin(), allA.end()), allA.end());
int MA = allA.size();
// posA_val -> posA_comp （圧縮後の値）
vector<vector<int>> posA(N);
for(int i = 0; i < N; i++){
for(ll x : posA_val[i]){
int c = int(lower_bound(allA.begin(), allA.end(), x) - allA.begin());
posA[i].push_back(c);
}
sort(posA[i].begin(), posA[i].end());
posA[i].erase(unique(posA[i].begin(), posA[i].end()), posA[i].end());
}
// 隣接ペア Bc の取りうる値を先読み（posB）
vector<vector<int>> posB(max(0, N-1));
if(N >= 2){
for(int i = 0; i < N-1; i++){
auto &a = posA[i], &b = posA[i+1];
int min_a = a[0], min_b = b[0];
vector<int> tmp;
// max(a_j, b_k) = a_j となる a_j は a_j >= min_b
auto ita = lower_bound(a.begin(), a.end(), min_b);
tmp.insert(tmp.end(), ita, a.end());
// max(a_j, b_k) = b_k となる b_k は b_k > min_a
auto itb = upper_bound(b.begin(), b.end(), min_a);
tmp.insert(tmp.end(), itb, b.end());
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
posB[i] = move(tmp);
}
}
// 3) BIT2D を構築
BIT2D bitA(N);
for(int i = 0; i < N; i++)
for(int y : posA[i])
bitA.fake_add(i, y);
bitA.init();
BIT2D bitB(N >= 2 ? N-1 : 0);
if(N >= 2){
for(int i = 0; i < N-1; i++)
for(int y : posB[i])
bitB.fake_add(i, y);
bitB.init();
}
// 4) 初期状態を BIT に登録
vector<int> Ac(N);
for(int i = 0; i < N; i++){
Ac[i] = int(lower_bound(allA.begin(), allA.end(), A[i]) - allA.begin());
bitA.update(i, Ac[i], +1);
}
vector<int> Bc;
if(N >= 2){
Bc.resize(N-1);
for(int i = 0; i < N-1; i++){
Bc[i] = max(Ac[i], Ac[i+1]);
bitB.update(i, Bc[i], +1);
}
}
// 5) クエリ処理
for(auto &q : qs){
if(q.type == 1){
int idx = q.i;
int oldc = Ac[idx];
int newc = int(lower_bound(allA.begin(), allA.end(), q.x) - allA.begin());
// A 更新
bitA.update(idx, oldc, -1);
bitA.update(idx, newc, +1);
Ac[idx] = newc;
// 隣接ペア更新
if(N >= 2){
if(idx > 0){
int i2 = idx-1;
int boc = Bc[i2], bnc = max(Ac[i2], Ac[i2+1]);
if(boc != bnc){
bitB.update(i2, boc, -1);
bitB.update(i2, bnc, +1);
Bc[i2] = bnc;
}
}
if(idx+1 < N){
int i2 = idx;
int boc = Bc[i2], bnc = max(Ac[i2], Ac[i2+1]);
if(boc != bnc){
bitB.update(i2, boc, -1);
bitB.update(i2, bnc, +1);
Bc[i2] = bnc;
}
}
}
}
else {
int l = q.l, r = q.r;
int len = r - l + 1;
// 閾値 k の最大値を二分探索
int low = 0, high = MA;
while(high - low > 1){
int mid = (low + high) >> 1;
int ge = bitA.query(l, r, mid, MA-1);
int lt_pairs = (l < r && N >= 2)
? bitB.query(l, r-1, 0, mid-1)
: 0;
ll H = ll(ge)*2 + lt_pairs;
if(H > len) low = mid;
else high = mid;
}
// 圧縮前の値を出力
cout << allA[low] << "\n";
}
}
return 0;
}