TIOJ-2140

2qbingxuan

2020-02-25

TIOJ , data-structure

殿壬愛序列

https://tioj.ck.tp.edu.tw/problems/2140

Description

給你一個長度為$N$的序列$a_1, a_2, \dots, a_N$，並且依序執行$Q$個操作，每個操作可能是

1 x y ：把$a_x$設成$y$
2 L R k ：對於每個$i \in [L, R]$，把$a_i$設成$\lfloor \frac{a_i}{k} \rfloor$。其中$\lfloor x \rfloor$代表不大於$x$的最大整數
3 L R ：請輸出$a_L, a _ {L+1}, \dots, a_R$的絕對眾數，如果絕對眾數不存在請輸出-1。一個數字若為$T$個數字的絕對眾數，代表這個數字至少在$T$個數字中出現$\lfloor \frac{T+2}{2} \rfloor$次。
$1 \leq N, Q \leq 10^5$
$1 \leq L \leq R \leq N$
$1 \leq x \leq N$
$0 \leq a_i, y \leq 10^9$
$1 \leq k \leq 10^9$

Solution

打架線段樹的裸題
對每個節點維護val和win，分別表示那個區間打贏的數字以及他贏了多少(?)
合併的時候假如兩個區間的val一樣，那麼他們的win就會相加
不同的話就是讓他們打架! win比較多的一方獲勝，但是必須減去對方的win
詳細請看node operator+的部分

一個區間的絕對眾數一定是打贏的數字，但是打贏的數字不一定是絕對眾數
得到一個區間打贏的數字之後，我們得知道這個數字到底在這個區間出現幾次
我們可以開rank tree對每個數字$x$紀錄$a_i=x$的index
只要知道$l,r$在rank tree的名次就能知道$l, r$之間有多少數字是$x$

至於區間除法就是暴力去做，如果該區間不全為$0$就遞迴計算直到葉節點
每個葉節點最多就被暴力除$\log C$次，每次暴力除最多影響另外$\log N$個節點，還有rank tree的一個$\log N$
即使有單點更新，也只會貢獻$\log C \log N$的複雜度
注意除以$1$不會讓$\log C$次是好的，不過他不會影響答案所以請記得略過

總複雜度大概是$\mathcal{O}((N+Q) \log N \log C)$吧

AC code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N = 100025;

unordered_map<int,rbt<int>> mp;
struct zkw{
    struct node {
        int val,win,isZero;
        node() : val(-1), win(0), isZero(0) {}
        node(int x) : val(x), win(1), isZero(x==0) {}
        inline friend node operator+(const node &a, const node &b) {
            node r;
            if(a.val == b.val) r.val=a.val, r.win=a.win+b.win;
            else if(a.win>b.win) r.val=a.val, r.win=a.win-b.win;
            else r.val=b.val, r.win=b.win-a.win;
            r.isZero = a.isZero&&b.isZero;
            return r;
        }
        friend void pr(const node &p) {
            cerr << p.val << ',' << p.win << '\n';
        }
    } seg[N<<1];
    int n;
    inline void init(int sz, int v[]) {
        n = sz;
        for(int i = 0; i < n; i++) seg[i+n] = node(v[i]), mp[v[i]].insert(i);
        for(int i = n-1; i >= 1; i--) seg[i] = seg[i<<1]+seg[i<<1|1];
    }
    void pull(int p) {
        for(; p; p>>=1) seg[p>>1] = seg[p]+seg[p^1];
    }
    inline void edit(int p, int k) {
        p+=n;
        mp[seg[p].val].erase(p-n);
        seg[p].val = k;
        seg[p].isZero = (seg[p].val == 0);
        mp[seg[p].val].insert(p-n);
        pull(p);
    }
    inline void brute(int i,int k) {
        if(seg[i].isZero) return;
        if(i < n) brute(i<<1,k), brute(i<<1|1,k), seg[i] = seg[i<<1]+seg[i<<1|1];
        //else edit(i-n,seg[i].val/k);
        else {
            mp[seg[i].val].erase(i-n);
            seg[i].val /= k;
            seg[i].isZero = (seg[i].val == 0);
            mp[seg[i].val].insert(i-n);
        }
    }
    inline void div(int l,int r,int k) {
        int L = l, R = r;
        for(l+=n,r+=n; l<r; l>>=1, r>>=1) {
            if(l&1) brute(l++,k);
            if(r&1) brute(--r,k);
        }
        pull(L+n), pull(R-1+n);
    }
    inline int winner(int l,int r) {
        node res = node();
        for(l+=n,r+=n; l<r; l>>=1, r>>=1) {
            //debug(l), debug(r);
            if(l&1) res = res+seg[l++];
            if(r&1) res = res+seg[--r];
        }
        return res.val;
    }
} sgt;
int n,q,v[N];
signed main() {
    mp.reserve(N);
    mp.max_load_factor(0.25);
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> v[i];
    sgt.init(n,v);
    for(int i = 0; i < q; i++) {
        int c,x,v,l,r;
        cin >> c;
        if(c == 1) {
            cin >> x >> v, --x;
            sgt.edit(x,v);
        }else if(c == 2) {
            cin >> l >> r >> v, --l;
            if(v!=1) sgt.div(l,r,v);
        }else if(c == 3) {
            cin >> l >> r, --l;
            v = sgt.winner(l,r);
            int cnt = mp[v].order_of_key(r) - mp[v].order_of_key(l);
            if(cnt > (r-l)/2) cout << v << '\n';
            else cout << -1 << '\n';
        }
    }
}