TIOJ 1169：氣球博覽會

TIOJ 1169：氣球博覽會

題目大意：給你 $n$ 個氣球排成一排，每個氣球都有一個顏色，有兩種操作，可以把位置 $p$ 的氣球顏色改成 $k$，或是問區間 $l\sim r$ 最長的連續區間沒有顏色 $k$ 這個氣球。

解法：可以先考慮如果是只有單一顏色的氣球，可以新增或移除氣球那麼可以用一個線段樹，維護最長的左連續長度，右連續長度和最長連續長度，每次合併。那如果有很多顏色，直接開 $2^{24}$ 個線段樹是不可能的，我們可以當有需要修改節點時再新增就好了，這樣大概是 $n\times log(n)$ 的空間。

$\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
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int MAX = 1 << 24;

struct Node {
    int lpos, rpos, lsum, rsum, sum;
} node[64 * SIZE];

int cnt, root[MAX + 5], color[SIZE];
int n, q, c;

void Pull (int pos, int l, int r) {
    int mid = (l + r) / 2, lp = node[pos].lpos, rp = node[pos].rpos;
    node[pos].lsum = node[lp].lsum == mid - l + 1 ? node[lp].sum + node[rp].lsum : node[lp].lsum;
    node[pos].rsum = node[rp].rsum == r - mid ? node[rp].sum + node[lp].rsum : node[rp].rsum;
    node[pos].sum = max ({node[lp].sum, node[rp].sum, node[lp].rsum + node[rp].lsum});
}

Node Merge (Node nl, Node nr) {
    auto [l, mid, Lls, Lrs, Ls] = nl;
    auto [_, r, Rls, Rrs, Rs] = nr;
    int lsum, rsum, sum;
    lsum = Lls == mid - l + 1 ? Ls + Rls : Lls;
    rsum = Rrs == r - mid ? Rs + Lrs : Rrs;
    sum = max ({Ls, Rs, Lrs + Rls});
    return {l, r, lsum, rsum, sum};
}

void build (int pos, int l, int r) {
    if (l == r) {
        node[pos].lsum = node[pos].rsum = node[pos].sum = 1;
    } else {
        node[pos].lpos = ++cnt;
        node[pos].rpos = ++cnt;
        int mid = (l + r) / 2;
        build (node[pos].lpos, l, mid);
        build (node[pos].rpos, mid + 1, r);
        Pull (pos, l, r);
    }
}

void update (int &pos, int l, int r, int p, bool i) {
    node[++cnt] = node[pos];
    pos = cnt;
    if (l == r) {
        node[pos].sum = node[pos].lsum = node[pos].rsum = !i;
    } else {
        int mid = (l + r) / 2;
        if (p <= mid) {
            update (node[pos].lpos, l, mid, p, i);
        } else {
            update (node[pos].rpos, mid + 1, r, p, i);
        }
        Pull (pos, l, r);
    }
}

Node query (int pos, int l, int r, int L, int R) {
    if (l == L && r == R) {
        Node nd = node[pos];
        nd.lpos = l, nd.rpos = r;
        return nd;
    }
    int mid = (L + R) / 2;
    if (r <= mid) {
        return query (node[pos].lpos, l, r, L, mid);
    }
    if (l > mid) {
        return query (node[pos].rpos, l, r, mid + 1, R);
    }
    return Merge (query (node[pos].lpos, l, mid, L, mid), query (node[pos].rpos, mid + 1, r, mid + 1, R));
}

void solve() {
    cin >> n >> q >> c;
    build (0, 1, n);
    FOR (i, 1, n) {
        cin >> color[i];
        update (root[color[i]], 1, n, i, 1);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 0) {
            int p, k;
            cin >> p >> k, p++;
            update (root[color[p]], 1, n, p, 0);
            update (root[k], 1, n, p, 1);
            color[p] = k;
        } else {
            int l, r, k;
            cin >> l >> r >> k, l++;
            cout << query (root[k], l, r, 1, n).sum << '\n';
        }
    }
}

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

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