TIOJ 2030：盩僰麌過街 人人喊打

TIOJ 2030：盩僰麌過街 人人喊打

題目大意：給你一個數列 $a_1\sim a_n$，每次有四種操作，第一種是將 $a_p = v$，第二種是將區間 $L, R$ 設一個強度為 $V$ 的雷射光，保證每個區間的左端點都是相異的，第三種是將左端點在 $L$ 的雷射光移除，第四種是問你區間 $L, R$ 共有多少強度，如果雷射光的區間是 $l, r$，且 $L\leq l \leq r\leq R$，那雷射光的強度就會被計算到，然後 $a_l\sim a_r$ 裡相異的 $a_i$ 會計算到。

解法：原本沒什麼想法，後來看了這篇文章後知道要用 $\text{CDQ}$ 分治，也就是要計算 $[L, R]$ 裡 $L\leq i\leq j\leq R$ 的答案時，可以分三種情況：$L\leq i\leq j\leq mid$、$mid + 1\leq i\leq j \leq R$ 和 $L\leq i\leq mid, mid + 1\leq j \leq R$，其中 $mid = \lfloor\frac{L+R}{2}\rfloor$，第一種和第二種可以遞迴下去，第三種則是要用一個快速的方法計算。假設我們現在有一個五元數組 $(l, r, t, v, is)$，代表一個區間，範圍是 $[l, r]$，被加入的時間是 $t$，強度是 $v$，$is$ 代表是不是詢問。那我們將這些區間按 $l$ 由大到小排好後，就可以開始分治。在遞迴完 $[L, mid], [mid + 1, R]$，數列有兩個性質：$[L, mid]$ 裡的 $l$ 恆大於等於 $[mid + 1, R]$ 裡的 $l$，$[L, mid], [mid + 1, R]$ 裡的 $t$ 都已經由小到大排好了，那就可以看當前要執行哪個區間的操作，若是第一個區間，那就是將 $is = 0$ 的 $\text{bit}$ 加值，若是第二個區間，那就是將 $is = 1$ 的答案加上 $\text{query}$。最後再把加值的扣回去就好了。

再來就是要怎麼把題目的操作變成以上形式，首先是雷射，我們可以對左端點紀錄它的右端點與強度，若是加入，那數組就是 $(l, r, i, v, 0)$，若是移除，那就是 $(l, r, i, -v, 0)$。然後我們可以用 $\text{set}$ 代表這個元素的所有位置，我們先把答案加上區間內可以重複的和，再來就是扣除的部分，如果一個區間涵蓋到兩個相鄰的位置，代表多算了一個，這也可以看做一個區間，所以我們每次可以加入位置和移除位置。因為 $n≒q$，最後的總時間複雜度是 $O(n\times\log^2(n))$，一個 $\log$ 是 $\text{bit}$ 的，一個是分治的。

$\text{Code：}$

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

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#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 = 1e5 + 5;
const int ASIZ = 7e5 + 5;

int n, m, q;
int a[SIZE];
set<int> s[SIZE];
pair<int, int> b[SIZE];
ll ans[SIZE], bit[SIZE];

struct Data {
    int l, r, t, v;
    bool is;
} op[ASIZ], tmp[ASIZ];

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

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

void Add (int x, int i, int t) {
    s[x].insert (i);
    auto it = s[x].find (i);
    if (it != s[x].begin()) op[++m] = {*prev (it), i, t, -x, 0};
    if (it != prev (s[x].end())) op[++m] = {i, *next (it), t, -x, 0};
    if (it != s[x].begin() && it != prev (s[x].end())) op[++m] = {*prev (it), *next (it), t, x, 0};
}

void Del (int x, int i, int t) {
    auto it = s[x].find (i);
    if (it != s[x].begin()) op[++m] = {*prev (it), i, t, x, 0};
    if (it != prev (s[x].end())) op[++m] = {i, *next (it), t, x, 0};
    if (it != s[x].begin() && it != prev (s[x].end())) op[++m] = {*prev (it), *next (it), t, -x, 0};
    s[x].erase (i);
}

void divide (int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    divide (l, mid);
    divide (mid + 1, r);
    for (int i = l, lpos = l, rpos = mid + 1; i <= r; i++) {
        if (rpos > r || (lpos <= mid && op[lpos].t <= op[rpos].t)) {
            if (op[lpos].is == 0) update (op[lpos].r, op[lpos].v);
            tmp[i] = op[lpos++];
        } else {
            if (op[rpos].is == 1) ans[op[rpos].t] += query (op[rpos].r);
            tmp[i] = op[rpos++];
        }
    }
    FOR (i, l, mid) update (op[i].r, -op[i].v);
    FOR (i, l, r) op[i] = tmp[i];
}

void solve() {
    cin >> n >> q;
    FOR (i, 1, n) {
        cin >> a[i];
        update (i, a[i]);
        Add (a[i], i, 0);
    }
    FOR (i, 1, q) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int p, v;
            cin >> p >> v;
            Del (a[p], p, i);
            update (p, v - a[p]);
            a[p] = v;
            Add (a[p], p, i);
        }
        if (ty == 2) {
            int l;
            cin >> l;
            auto &[r, v] = b[l];
            cin >> r >> v;
            op[++m] = {l, r, i, v, 0};
        }
        if (ty == 3) {
            int l;
            cin >> l;
            auto &[r, v] = b[l];
            op[++m] = {l, r, i, -v, 0};
        }
        if (ty == 4) {
            int l, r;
            cin >> l >> r;
            op[++m] = {l, r, i, 0, 1};
            ans[i] = query (r) - query (l - 1);
        }
    }
    fill (bit, bit + n + 1, 0);
    sort (op + 1, op + m + 1, [] (auto x, auto y) {
        return x.l != y.l ? x.l > y.l : x.is < y.is;
    });
    divide (1, m);
    FOR (i, 1, q) if (ans[i]) cout << ans[i] << '\n';
}

int main() {
    TIOJQQ;
    solve();
}

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