TIOJ 2140：殿壬愛序列

TIOJ 2140：殿壬愛序列

題目大意：給你一個數列 $a_1\sim a_n$，每次有三種操作，第一種是將 $a_p = k$，第二種是讓 $l\leq i \leq r$ 的 $a_i = \lfloor\frac{a_i}{k}\rfloor$，第三種是輸出 $a_l\sim a_r$ 的絕對眾數 $x$，也就是 $x$ 的出現次數 $c$ 要滿足 $2\times c > r - l + 1$，否則輸出 $-1$。

解法：首先可以知道每次除以 $k>1$ 除 $\log(C)$ 次就會變成 $0$ 了，所以暴力是沒問題的，再來要找到一個區間可能的絕對眾數如果要暴力找，那可以維護兩個變數 $w, b$，$w$ 代表目前獲勝的數字，$b$ 代表這個數字目前的血量，如果當前數字等於 $w$，那就將 $b$ 加一，否則將 $b$ 減一，如果操作完 $b < 0$，那就將 $w$ 換成當前的數字，$b$ 設成 $0$。這個想法可以用在線段樹上，於是就可以 $O(\log(n))$ 找出可能的絕對眾數。找到可能的絕對眾數後，就可以用 $\text{Treap}$ 找出在 $l\sim r$ 共有幾個數字，最後複雜度為 $O((n + q)\times\log(n)\times\log(C))$，原因是原本的 $n$ 個數字加新增的 $q$ 個數字，每個除 $\log(C)$ 次，每次都會動到 $\text{Treap}$ 花 $O(\log(n))$ 的複雜度。

$\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

#define lpos pos*2
#define rpos pos*2+1

mt19937 seed (time (NULL));
#define rnd(l,r) uniform_int_distribution<int>(l,r)(seed)

const int SIZE = 1e5 + 5;

struct Treap {
    int val, siz = 1, prior = rnd (0, 2e9);
    Treap *ls = NULL, *rs = NULL;
    Treap() {}
    Treap (int val) : val (val) {}
};

int siz (Treap *t) {
    return t == NULL ? 0 : t->siz;
}

void Pull (Treap *t) {
    t->siz = siz (t->ls) + siz (t->rs) + 1;
}

Treap *Merge (Treap *a, Treap *b) {
    if (a == NULL || b == NULL) return a != NULL ? a : b;
    if (a->prior > b->prior) {
        a->rs = Merge (a->rs, b);
        Pull (a);
        return a;
    } else {
        b->ls = Merge (a, b->ls);
        Pull (b);
        return b;
    }
}

void Split (Treap *t, Treap *&a, Treap *&b, int k) {
    if (t == NULL) {a = b = NULL; return;}
    if (t->val <= k) {
        a = t;
        Split (t->rs, a->rs, b, k);
        Pull (a);
    } else {
        b = t;
        Split (t->ls, a, b->ls, k);
        Pull (b);
    }
}

struct Node {
    int w, b;
    Node operator + (const Node &x) const {
        Node re;
        if (w == x.w) re.w = w, re.b = b + x.b;
        else {
            re.w = b >= x.b ? w : x.w;
            re.b = max (b, x.b) - min (b, x.b);
        }
        return re;
    }
} node[4 * SIZE];

int n, q;
int a[SIZE];
map<int, Treap*> mp;

void build (int pos, int l, int r) {
    if (l == r) {
        cin >> a[l];
        node[pos] = {a[l], 1};
        mp[a[l]] = Merge (mp[a[l]], new Treap (l));
        return;
    }
    int mid = (l + r) / 2;
    build (lpos, l, mid);
    build (rpos, mid + 1, r);
    node[pos] = node[lpos] + node[rpos];
}

void Upd (int pos, int l, int r, int p, int x) {
    if (l == r) {
        Treap *t = mp[a[l]], *t1, *t2;
        Split (t, t1, t, l - 1);
        Split (t, t, t2, l);
        mp[a[l]] = Merge (t1, t2);
        node[pos].w = a[l] = x;
        Split (mp[a[l]], t1, t2, l - 1);
        mp[a[l]] = Merge (t1, Merge (t, t2));
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) Upd (lpos, l, mid, p, x);
    else Upd (rpos, mid + 1, r, p, x);
    node[pos] = node[lpos] + node[rpos];
}

void Div (int pos, int l, int r, int L, int R, int x) {
    if (node[pos].w == 0 && node[pos].b == R - L + 1) return;
    if (L == R) {
        Treap *t = mp[a[l]], *t1, *t2;
        Split (t, t1, t, l - 1);
        Split (t, t, t2, l);
        mp[a[l]] = Merge (t1, t2);
        node[pos].w = a[l] /= x;
        Split (mp[a[l]], t1, t2, l - 1);
        mp[a[l]] = Merge (t1, Merge (t, t2));
        return;
    }
    int mid = (L + R) / 2;
    if (r <= mid) Div (lpos, l, r, L, mid, x);
    else if (l > mid) Div (rpos, l, r, mid + 1, R, x);
    else {
        Div (lpos, l, mid, L, mid, x);
        Div (rpos, mid + 1, r, mid + 1, R, x);
    }
    node[pos] = node[lpos] + node[rpos];
}

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

void solve() {
    cin >> n >> q;
    build (1, 1, n);
    while (q--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int p, k;
            cin >> p >> k;
            Upd (1, 1, n, p, k);
        }
        if (ty == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            if (k != 1) Div (1, l, r, 1, n, k);
        }
        if (ty == 3) {
            int l, r, k;
            cin >> l >> r;
            auto [w, b] = query (1, l, r, 1, n);
            Treap *t = mp[w], *t1, *t2;
            Split (t, t1, t, l - 1);
            Split (t, t, t2, r);
            k = siz (t);
            mp[w] = Merge (t1, Merge (t, t2));
            if (2 * k > r - l + 1) cout << w << '\n';
            else cout << "-1\n";
        }
    }
}

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

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