TIOJ 1840：Coding Days コーディングデイス

TIOJ 1840：Coding Days コーディングデイス

題目大意：給你陣列 $a[n]$，每次有三種操作，第一種是輸出區間 $[ l, r ]$ 的第 $k$ 小值，第二種是將 $a[p]$ 改成 $k$，第三種直接輸出 $7122$。

解法：可以用整體二分搜搭配 $\text{BIT}$，而且可以先離散化處理。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back

const int SIZE = 5e4 + 5, QSIZE = 1e4 + 5;

struct Ask {
    int id, t, x, y, k;
    Ask() {}
    Ask (int id, int t, int x, int y, int k) : id (id), t (t), x (x), y (y), k (k) {}
} q[SIZE + 2 * QSIZE], q1[SIZE + 2 * QSIZE], q2[SIZE + 2 * QSIZE];

int n, m, a[SIZE], bit[SIZE], ans[QSIZE];

void update (int p, int x) {
    for (; p <= n; p += p & -p)
        bit[p] += x;
}

int query (int p) {
    int re = 0;
    for (; p; p -= p & -p)
        re += bit[p];
    return re;
}

void divide (int l, int r, int L, int R) {
    if (L > R)
        return;
    if (l == r) {
        FOR (i, L, R) ans[q[i].id] = l;
        return;
    }
    
    int cnt1 = 0, cnt2 = 0, mid = (l + r) / 2;
    FOR (i, L, R) {
        if (q[i].t == 1) {
            int num = query (q[i].y) - query (q[i].x - 1);
            if (q[i].k <= num)
                q1[++cnt1] = q[i];
            else {
                q[i].k -= num;
                q2[++cnt2] = q[i];
            }
        } else {
            if (q[i].y <= mid) {
                update (q[i].x, q[i].k);
                q1[++cnt1] = q[i];
            } else
                q2[++cnt2] = q[i];
        }
    }
    
    FOR (i, 1, cnt1) {
        if (q1[i].t == 2)
            update (q1[i].x, -q1[i].k);
        q[L + i - 1] = q1[i];
    }
    FOR (i, 1, cnt2) q[L + cnt1 + i - 1] = q2[i];
    divide (l, mid, L, L + cnt1 - 1);
    divide (mid + 1, r, L + cnt1, R);
}

void solve() {
    cin >> n >> m;
    int qsiz = 0, id = 0;
    vector<int> lis;
    
    FOR (i, 1, n) {
        cin >> a[i];
        lis.pb (a[i]);
        q[++qsiz] = {0, 2, i, a[i], 1};
    }
    FOR (i, 1, m) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            int k;
            cin >> k;
            q[++qsiz] = {++id, 1, x, y, k};
        } else if (t == 2) {
            q[++qsiz] = {0, 2, x, a[x], -1};
            q[++qsiz] = {0, 2, x, y, 1};
            lis.pb (a[x] = y);
        } else
            ans[++id] = -1;
    }
    
    sort (lis.begin(), lis.end());
    lis.erase (unique (lis.begin(), lis.end()), lis.end());
    FOR (i, 1, qsiz) {
        if (q[i].t == 2)
            q[i].y = lower_bound (lis.begin(), lis.end(), q[i].y) - lis.begin();
    }
    divide (0, lis.size() - 1, 1, qsiz);
    FOR (i, 1, id) cout << (ans[i] == -1 ? 7122 : lis[ans[i]]) << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt;
    cin >> tt;
    while (tt--)
        solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！