TIOJ 2140

Created2021-02-07Updated2021-02-07

連結

題意

給一個長度為aa的序列，請支援三種操作：

  1. 給定p,kp, k，將apa_p設成kk
  2. 給定l,r,kl, r, k，∀l≤i≤r,ai=⌊aik⌋\forall l \leq i \leq r, a_i = \lfloor \frac{a_i}{k} \rfloor
  3. 給定l,rl, r，輸出al,al+1,...,ara_l, a_{l + 1}, ..., a_r的絕對多數，若不存在輸出-1

TT個數若存在絕對多數xx，代表xx出現的次數≥⌊T+22⌋\geq \lfloor \frac{T + 2}{2} \rfloor

(1≤n,q≤105)(1 \leq n, q \leq 10^5)

解法

首先先說明最基本的，如何O(n)\mathcal{O}(n)找絕對多數
可以採用擂台(?的想法，假設現在站在擂台上的數字為xx，他的血量為hh，則

  1. 若出現的數字為xx，則他的血量+1
  2. 否則他的血量-1，若血量為0就換一個數站上去

很trivial的結論，最後還在擂台上的數字才有可能是絕對多數
所以只要再花O(n)\mathcal{O}(n)的時間判斷他是不是絕對多數即可
寫成扣大概長這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector <int> a(n);
int x = -1, h = 0;
for (int i = 0; i < n; ++i) {
    if (x == a[i]) {
        h++;
    } else {
        if (h == 0) x = a[i], h = 1;
        else h--; 
    }
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
    if (a[i] == x) cnt++;
}
if (cnt < n / 2 + 1) cout << -1 << endl;
else cout << x << endl;

好，可4現在是多筆詢問還有奇怪的除法捏，怎麼辦？

現在我們開一顆線段樹，每個節點存下該區間現在還在擂台上的數以及他的血量
節點merge可以做到O(1)\mathcal{O}(1)，所以建樹複雜度沒有問題，是好好的O(n)\mathcal{O}(n)
這樣一來再回頭看一下操作：

  1. 單點修改
    直接改就好，複雜度O(logn)\mathcal{O}(logn)
  2. 區間除法
    因為k=1k = 1不會影響陣列，所以可以視為k≥2k \geq 2，這樣一來每個數最多只會被除logClogC次
    又每次修改只是單點修改，所以均攤下來複雜度會是O((n+q))logC)\mathcal{O}((n + q))logC)，完美
    實作上可以在每個節點多紀錄區間的最大值，大於0再進行操作
  3. 區間絕對多數
    採取前面擂台的方式，找出還在擂台上的數字，再判斷他是不是絕對多數即可
    可以使用pbds或treap計算出一個區間內某數字的出現次數
    這樣就做完啦~

複雜度為O((n+q)logC+n+qlogn)\mathcal{O}((n + q)logC + n + qlogn)反正是好的就對了

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 2008, logN = 17, K = 333;

tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;

struct Seg {
    int l, r, m, val, cnt, mx;
    Seg *ch[2];
    Seg (int _l, int _r, vector<int> &a) : l(_l), r(_r), m(l + r >> 1) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m, a);
            ch[1] = new Seg(m, r, a);
            pull();
        } else {
            val = mx = a[l];
            oset.insert(mp(a[l], l));
            cnt = 1;
        }
    }
    void pull() {
        if (ch[0]->val == ch[1]->val) {
            val = ch[0]->val;
            cnt = ch[0]->cnt + ch[1]->cnt;
        } else if (ch[0]->cnt > ch[1]->cnt) {
            val = ch[0]->val;
            cnt = ch[0]->cnt - ch[1]->cnt;
        } else {
            val = ch[1]->val;
            cnt = ch[1]->cnt - ch[0]->cnt;
        }
        mx = max(ch[0]->mx, ch[1]->mx);
    }
    void modify(int a, int b, int k) {
        if (r - l == 1) {
            oset.erase(mp(val, l));
            val = mx = val / k;
            oset.insert(mp(val, l));
        } else {
            if (a < m && ch[0]->mx > 0) ch[0]->modify(a, b, k);
            if (m < b && ch[1]->mx > 0) ch[1]->modify(a, b, k);
            pull();
        }
    }
    void set(int p, int v) {
        if (r - l == 1) {
            oset.erase(mp(val, l));
            val = mx = v;
            oset.insert(mp(val, l));
        } else {
            ch[p >= m]->set(p, v);
            pull();
        }
    }
    pii query(int a, int b) {
        if (a <= l && r <= b) return mp(val, cnt);
        pii cur = mp(-1, 0);
        if (a < m) {
            pii tmp = ch[0]->query(a, b);
            if (cur.X == tmp.X) {
                cur.Y += tmp.Y;
            } else {
                if (cur.Y <= tmp.Y) swap(cur, tmp);
                cur.Y -= tmp.Y;
            }
        }
        if (m < b) {
            pii tmp = ch[1]->query(a, b);
            if (cur.X == tmp.X) {
                cur.Y += tmp.Y;
            } else {
                if (cur.Y <= tmp.Y) swap(cur, tmp);
                cur.Y -= tmp.Y;
            }
        }
        return cur;
    }
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    Seg root(0, n, a);
    while (q--) {
        int t, l, r, k;
        cin >> t >> l >> r, l--;
        if (t == 1) {
            root.set(l, r);
        } else if (t == 2) {
            cin >> k;
            if (k > 1) root.modify(l, r, k);
        } else {
            pii tmp = root.query(l, r);
            if (oset.order_of_key(mp(tmp.X, r)) - oset.order_of_key(mp(tmp.X, l)) < (r - l) / 2 + 1) {
                cout << "-1\n";
            } else {
                cout << tmp.X << '\n';
            }
        }
    }
}