結果

問題 No.3122 Median of Medians of Division
ユーザー shibh308
提出日時 2025-04-20 06:35:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 7,004 bytes
コンパイル時間 2,942 ms
コンパイル使用メモリ 217,804 KB
実行使用メモリ 96,076 KB
最終ジャッジ日時 2025-04-20 06:35:24
合計ジャッジ時間 11,185 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// --- Fenwick Tree (1-indexed internally) ---
struct Fenwick {
    int n;
    vector<int> t;
    Fenwick(int _n=0): n(_n), t(n+1,0) {}
    void init(int _n){
        n = _n;
        t.assign(n+1, 0);
    }
    // add v at index i (0-based)
    void update(int i, int v){
        for(++i; i <= n; i += i & -i)
            t[i] += v;
    }
    // sum [0..i] (0-based)
    int query(int i) const {
        int s = 0;
        for(++i; i > 0; i -= i & -i)
            s += t[i];
        return s;
    }
    // sum [l..r]
    int query(int l, int r) const {
        if(l > r) return 0;
        return query(r) - (l? query(l-1) : 0);
    }
};

// --- イベント構造体 ---
struct Upd {
    int time;    // イベント発生時刻：0 が「初期値」、1..Q がクエリ番号
    int pos;     // 更新位置 (A: [0..N-1], B: [0..N-2])
    int c;       // 圧縮後の値
    int delta;   // +1 or -1
};
struct Query {
    int time;    // クエリ発生時刻（1..Q）
    int l, r;    // range [l..r]
    int len;     // = r-l+1
    int id;      // 元のクエリ順序（1..Q）
    int ans;     // 探索後の圧縮値
};

// 再帰的 Parallel Binary Search
// qids: まだ答えが確定していないクエリのインデックス集合
// valL..valR: この区間で二分探索中。最終的に [val, val+1) になる
void solve(int valL, int valR,
           vector<int>& qids,
           const vector<Upd>& Aev,
           const vector<Upd>& Bev,
           vector<Query>& Qs,
           Fenwick& bitA,
           Fenwick& bitB)
{
    if(qids.empty()) return;
    if(valL + 1 == valR){
        // この閾値に確定
        for(int qi : qids)
            Qs[qi].ans = valL;
        return;
    }
    int mid = (valL + valR) >> 1;

    // クエリ時間順に並べる
    vector<int> order = qids;
    sort(order.begin(), order.end(),
         [&](int a, int b){ return Qs[a].time < Qs[b].time; });

    vector<int> leftQ, rightQ;
    vector<int> appliedA, appliedB;
    int pA = 0, pB = 0;
    // BIT はこの recursion の開始時点ですべて 0 であることを仮定
    for(int qi : order){
        int qt = Qs[qi].time;
        // A-events を時刻 qt まで流し込む
        while(pA < (int)Aev.size() && Aev[pA].time <= qt){
            if(Aev[pA].c >= mid){
                bitA.update(Aev[pA].pos, Aev[pA].delta);
                appliedA.push_back(pA);
            }
            ++pA;
        }
        // B-events を時刻 qt まで流し込む
        while(pB < (int)Bev.size() && Bev[pB].time <= qt){
            if(Bev[pB].c < mid){
                bitB.update(Bev[pB].pos, Bev[pB].delta);
                appliedB.push_back(pB);
            }
            ++pB;
        }
        // 条件判定
        int ge = bitA.query(Qs[qi].l, Qs[qi].r);
        int lt_pairs = (Qs[qi].l < Qs[qi].r
                        ? bitB.query(Qs[qi].l, Qs[qi].r - 1)
                        : 0);
        if(2LL * ge + lt_pairs > Qs[qi].len)
            rightQ.push_back(qi);
        else
            leftQ.push_back(qi);
    }
    // ロールバック
    for(int idx : appliedA){
        bitA.update(Aev[idx].pos, -Aev[idx].delta);
    }
    for(int idx : appliedB){
        bitB.update(Bev[idx].pos, -Bev[idx].delta);
    }
    // 再帰
    solve(valL, mid,   leftQ, Aev, Bev, Qs, bitA, bitB);
    solve(mid,  valR, rightQ, Aev, Bev, Qs, bitA, bitB);
}

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 InQ { int type, i, l, r; ll x; };
    vector<InQ> in(Q+1);
    // 先読みして座標圧縮のための候補を集める
    vector<vector<ll>> posA(N);
    for(int i = 0; i < N; i++)
        posA[i].push_back(A[i]);

    for(int qi = 1; qi <= Q; qi++){
        cin >> in[qi].type;
        if(in[qi].type == 1){
            cin >> in[qi].i >> in[qi].x;
            --in[qi].i;
            posA[in[qi].i].push_back(in[qi].x);
        } else {
            cin >> in[qi].l >> in[qi].r;
            --in[qi].l; --in[qi].r;
        }
    }

    // 全体圧縮
    vector<ll> all;
    all.reserve(N + Q);
    for(int i = 0; i < N; i++){
        auto &v = posA[i];
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        for(ll x : v) all.push_back(x);
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    int MA = all.size();

    // 初期 Ac, Bc を計算
    vector<int> Ac(N), Bc(max(0, N-1));
    for(int i = 0; i < N; i++){
        Ac[i] = int(lower_bound(all.begin(), all.end(), A[i]) - all.begin());
    }
    for(int i = 0; i + 1 < N; i++){
        Bc[i] = max(Ac[i], Ac[i+1]);
    }

    // イベント生成
    vector<Upd> Aev, Bev;
    Aev.reserve(2*(N + Q));
    Bev.reserve(2*(max(0,N-1) + Q));
    // time=0: 初期値を add
    for(int i = 0; i < N; i++){
        Aev.push_back({0, i, Ac[i], +1});
    }
    for(int i = 0; i + 1 < N; i++){
        Bev.push_back({0, i, Bc[i], +1});
    }

    // queries list
    vector<Query> Qs;
    Qs.reserve(Q);

    // カレント配列
    vector<int> curA = Ac, curB = Bc;
    for(int qi = 1; qi <= Q; qi++){
        if(in[qi].type == 1){
            int i = in[qi].i;
            int oldc = curA[i];
            int newc = int(lower_bound(all.begin(), all.end(), in[qi].x) - all.begin());
            // A のイベント
            Aev.push_back({qi, i, oldc, -1});
            Aev.push_back({qi, i, newc, +1});
            curA[i] = newc;
            // B のイベント （両隣）
            if(i > 0){
                int p = i-1;
                int ob = curB[p];
                int nb = max(curA[p], curA[p+1]);
                Bev.push_back({qi, p, ob, -1});
                Bev.push_back({qi, p, nb, +1});
                curB[p] = nb;
            }
            if(i+1 < N){
                int p = i;
                int ob = curB[p];
                int nb = max(curA[p], curA[p+1]);
                Bev.push_back({qi, p, ob, -1});
                Bev.push_back({qi, p, nb, +1});
                curB[p] = nb;
            }
        } else {
            // クエリを保存
            Qs.push_back({ qi,
                           in[qi].l, in[qi].r,
                           in[qi].r - in[qi].l + 1,
                           qi, /* id= time */
                           -1 });
        }
    }

    // Fenwick 準備
    Fenwick bitA(N), bitB(max(0, N-1));

    // qids 初期化
    vector<int> qids(Qs.size());
    iota(qids.begin(), qids.end(), 0);

    // 再帰実行
    solve(0, MA, qids, Aev, Bev, Qs, bitA, bitB);

    // 出力：時刻順に並んでいる Qs を使い、全体入力を走査して type2 のみ出力
    // Qs[i].ans は「圧縮後の index」
    // all[Qs[i].ans] が実際の値
    for(auto &q : Qs){
        cout << all[q.ans] << "\n";
    }
    return 0;
}
0