Shawn's Blog

Posted on Edited on In 
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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 1e5;
int t, n, c[N], l[N], r[N], order[N], p[N], sz[N], cnt;
struct Cmp{
    bool operator() (const int x, const int y) const {
        return r[x] != r[y] ? r[x] < r[y] : x < y;
    }
};
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void connect(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) {
        if (sz[x] > sz[y]) swap(x, y);
        p[px] = py;
        sz[y] += sz[x];
        --cnt;
    }
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        cnt = n;
        vector<set<int, Cmp>> open(2);
        for (int i = 0; i < n; ++i) {
            scanf("%d%d%d", &c[i], &l[i], &r[i]);
            p[i] = order[i] = i, sz[i] = 1;
        }
        sort(order, order + n, [&](int x, int y) {
            return l[x] != l[y] ? l[x] < l[y] : 
                (r[x] != r[y] ? r[x] < r[y] : x < y);
        });
        for (int i = 0; i < n; ++i) {
            int o = order[i];
            int lo = l[o], ro = r[o], co = c[o], xc = co ^ 1;
            auto &cs = open[co], &xs = open[xc];
            while (cs.size() && r[*cs.begin()] < lo) cs.erase(cs.begin());
            while (xs.size() && r[*xs.begin()] < lo) xs.erase(xs.begin());
            cs.insert(o);
            while (xs.size()) {
                auto it = xs.begin();
                connect(o, *it);
                if (xs.size() > 1) xs.erase(it);
                else break;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

Posted on Edited on In

原题为 HDU 1754 I Hate It。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200001;
int n, m, a, b, w[N], tr[N];
char op[2];
int lowbit(int x) {
    return x & -x;
}
void update(int i) {
    for (; i <= n; i += lowbit(i)) {
        tr[i] = w[i];
        int li = lowbit(i);
        for (int j = 1; j < li; j <<= 1)
            tr[i] = max(tr[i], tr[i - j]);
    }
}
int query(int l, int r) {
    int ans = 0;
    while (r >= l) {
        ans = max(ans, w[r]);
        for (--r; r - lowbit(r) > l; r -= lowbit(r))
            ans = max(ans, tr[r]);
    }
    return ans;
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(tr, 0, sizeof(tr));
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            update(i);
        }
        while (m--) {
            scanf("%s%d%d", op, &a, &b);
            if (*op == 'Q') printf("%d\n", query(a, b));
            else w[a] = b, update(a);
        } 
    }
    return 0;
}
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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200001, INF = -0x3f3f3f3f;
int n, m, a, b;
char op[2];
struct Node {
    int l, r, max_val;
} tr[N << 2];
void pushup(int u) {
    tr[u].max_val = max(tr[u << 1].max_val, tr[u << 1 | 1].max_val);
}
void build(int u, int l, int r) {
    tr[u] = {l, r, 0};
    if (l == r) {
        scanf("%d", &a), tr[u].max_val = a;
    } else {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].max_val;
    int mid = (tr[u].l + tr[u].r) >> 1, ans = INF;
    if (l <= mid) ans = query(u << 1, l, r);
    if (r > mid) ans = max(ans, query(u << 1 | 1, l, r));
    return ans;
}
void update(int u, int x, int k) {
    if (tr[u].l == tr[u].r) tr[u].max_val = k;
    else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) update(u << 1, x, k);
        else update(u << 1 | 1, x, k);
        pushup(u);
    }
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        build(1, 1, n);
        while (m--) {
            scanf("%s%d%d", op, &a, &b);
            if (*op == 'Q') printf("%d\n", query(1, a, b));
            else update(1, a, b);
        } 
    }
    return 0;
}
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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200001, INF = -0x3f3f3f3f;
int n, _n, m, a, b;
char op[2];
vector<int> tr;
int query(int u, int l, int r, int L, int R) {
    if (R < l || L > r) return INF;
    if (L <= l && r <= R) return tr[u];
    int mid = (l + r) >> 1, ans = INF;
    if (l <= mid) ans = query(u << 1, l, mid, L, R);
    if (r > mid) ans = max(ans, query(u << 1 | 1, mid + 1, r, L, R));
    return ans;
}
void update(int x, int k) {
    int i = _n + x;
    tr[i] = k;
    while (i > 1) {
        i >>= 1;
        tr[i] = max(tr[i << 1], tr[i << 1 | 1]);
    }
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        _n = n;
        while (__builtin_popcount(_n) != 1) _n++;
        tr = vector<int>(2 * _n, INF);
        for (int i = 0; i < n; ++i) scanf("%d", &tr[_n + i]);
        for (int i = _n - 1; i >= 1; --i) tr[i] = max(tr[i << 1], tr[i << 1 | 1]);
        while (m--) {
            scanf("%s%d%d", op, &a, &b);
            if (*op == 'Q') printf("%d\n", query(1, 0, _n - 1, a - 1, b - 1));
            else update(a - 1, b);
        } 
    }
    return 0;
}

Posted on Edited on In 
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500001, INF = 0x3f3f3f3f;
int n, m, w[N], l, r, t1[N], t2[N];
int lowbit(int x) {
    return x & -x;
}
void update(int i) {
    for (; i <= n; i += lowbit(i)) {
        t1[i] = t2[i] = w[i];
        int li = lowbit(i);
        for (int j = 1; j < li; j <<= 1)
            t1[i] = min(t1[i], t1[i - j]), t2[i] = max(t2[i], t2[i - j]);
    }
}
int find_max(int l, int r) {
    int ans = 0;
    while (r >= l) {
        ans = max(ans, w[r]);
        for (--r; r - lowbit(r) > l; r -= lowbit(r))
            ans = max(ans, t2[r]);
    }
    return ans;
}
int find_min(int l, int r) {
    int ans = INF;
    while (r >= l) {
        ans = min(ans, w[r]);
        for (--r; r - lowbit(r) > l; r -= lowbit(r))
            ans = min(ans, t1[r]);
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    memset(t1, 0x3f, sizeof(t1));
    memset(t2, -0x3f, sizeof(t2));
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
        update(i);
    }
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", find_max(l, r) - find_min(l, r));
    }
    return 0;
}
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
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, h, l, r;
const int N = 500001, INF = 0x3f3f3f3f;
struct Node {
    int l, r, min_val, max_val;
} tr[N << 2];
void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l == r) {
        scanf("%d", &h), tr[u].min_val = tr[u].max_val = h;
    } else {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u].min_val = min(tr[u << 1].min_val, tr[u << 1 | 1].min_val);
        tr[u].max_val = max(tr[u << 1].max_val, tr[u << 1 | 1].max_val);
    }
}
int find_max(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].max_val;
    int mid = (tr[u].l + tr[u].r) >> 1, ans = -INF;
    if (l <= mid) ans = find_max(u << 1, l, r);
    if (r > mid) ans = max(ans, find_max(u << 1 | 1, l, r));
    return ans;
}
int find_min(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].min_val;
    int mid = (tr[u].l + tr[u].r) >> 1, ans = INF;
    if (l <= mid) ans = find_min(u << 1, l, r);
    if (r > mid) ans = min(ans, find_min(u << 1 | 1, l, r));
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", find_max(1, l, r) - find_min(1, l, r));
    }
    return 0;
}
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
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 500001, M = 19;
int n, m, l, r, h[N], f1[N][M], f2[N][M];
void init() {
    for (int j = 0; j < M; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            if (!j) f1[i][j] = f2[i][j] = h[i];
            else
                f1[i][j] = min(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]),
                f2[i][j] = max(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
}
int find_max(int l, int r) {
    int len = r - l + 1, k = log(len) / log(2);
    return max(f2[l][k], f2[r - (1 << k) + 1][k]);
}
int find_min(int l, int r) {
    int len = r - l + 1, k = log(len) / log(2);
    return min(f1[l][k], f1[r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    init();
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", find_max(l, r) - find_min(l, r));
    }
    return 0;
}

Posted on Edited on In 
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
// Reference: https://www.cnblogs.com/AC-Phoenix/p/4347347.html
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 500001, INF = 0x3f3f3f3f;
int n, m, a[N], l[N], r[N], order[N], ans[N], tr[N];
unordered_map<int , int> mp;
int main() {
    int i, j;
    scanf("%d%d", &n ,&m);
    for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (i = 1; i <= m; ++i) scanf("%d%d", &l[i], &r[i]), order[i] = i;
    memset(tr, 0x3f, sizeof(tr));
    memset(ans, 0x3f, sizeof(ans));
    sort(order + 1, order + 1 + m, [&] (int i, int j) {
        return r[i] < r[j]; // sort queries by r.
    });
    for (i = j = 1; i <= m; ++i) { // for each query.
        int o = order[i];
        while (j <= r[o]) { // deal with numbers within [1, r].
            if (mp[a[j]]) { // have met a[j] before.
                int pos = mp[a[j]];
                for(int k = pos; k; k -= k & -k)
                    // stored the info (min value) into binary indexed tree.
                    tr[k] = min(tr[k], j - pos);
            }
            mp[a[j]] = j;
            ++j;
        }
        for(int k = l[o]; k <= r[o]; k += k & -k)
            ans[o] = min(ans[o], tr[k]);
    }
    for(i = 1; i <= m; ++i)
        printf("%d\n", ans[i] == INF? -1: ans[i]);
}

Posted on Edited on In 
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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200001;
int n, m, a[N], nums[N], root[N], idx, l, r, k, len;
struct Node {
    int l, r, cnt;
} tr[N * 4 + N * 18];
int find(int x) {
    return lower_bound(nums + 1, nums + 1 + len, x) - nums;
}
int build(int l, int r) {
    int p = ++idx;
    if (l == r) return p;
    int mid = (l + r) >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}
int insert(int p, int l, int r, int x) {
    int q = ++idx;
    tr[q] = tr[p];
    if (l == r) {
        ++tr[q].cnt;
        return q;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}
int query(int q, int p, int l, int r, int k) {
    if (l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt, mid = (l + r) >> 1;
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        nums[i]= a[i];
    }
    sort(nums + 1, nums + 1 + n);
    len = unique(nums + 1, nums + 1 + n) - nums - 1;
    root[0] = build(1, len + 1);
    for (int i = 1; i <= n; ++i)
        root[i] = insert(root[i - 1], 1, len, find(a[i]));
    while (m--) {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[r], root[l - 1], 1, len, k)]);
    }
    return 0;
}

Posted on Edited on In 
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
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
const int N = 100001, INF = 1e8;
int n, op, x, root, idx;
struct Node {
    int l, r;
    int key, fix;
    int cnt, size;
} tr[N];
void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key) {
    tr[++idx].key = key;
    tr[idx].fix = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}
void build() {
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);
}
void zig(int &p) {
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}
void zag(int &p) {
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}
void insert(int &p, int key) {
    if (!p) p = get_node(key);
    else if (tr[p].key == key) ++tr[p].cnt;
    else if (tr[p].key > key) {
        insert(tr[p].l, key);
        if (tr[tr[p].l].fix > tr[p].fix) zig(p);
    } else {
        insert(tr[p].r, key);
        if (tr[tr[p].r].fix > tr[p].fix) zag(p);
    }
    pushup(p);
}
void remove(int &p, int key) {
    if (!p) return;
    if (tr[p].key == key) {
        if (tr[p].cnt > 1) --tr[p].cnt;
        else if (tr[p].l || tr[p].r) {
            if (!tr[p].r || tr[tr[p].l].fix > tr[tr[p].r].fix) {
                zig(p);
                remove(tr[p].r, key);
            } else {
                zag(p);
                remove(tr[p].l, key);
            }
        } else p = 0;
    } else if (tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);
    pushup(p);
}
int get_rank_by_key(int p, int key) {
    if (!p) return 0;
    if (tr[p].key == key) return tr[tr[p].l].size + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}
int get_key_by_rank(int p, int rank) {
    if (!p) return INF;
    if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int get_prev(int p, int key) {
    if (!p) return -INF;
    if (tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}
int get_next(int p, int key) {
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
} 
int main() {
    ios::sync_with_stdio(false);
    srand(time(nullptr));
    build();
    cin >> n;
    while (n--) {
        cin >> op >> x;
        if (op == 1) insert(root, x);
        else if (op == 2) remove(root, x);
        else if (op == 3) cout << get_rank_by_key(root, x) - 1 << endl;
        else if (op == 4) cout << get_key_by_rank(root, x + 1) << endl;
        else if (op == 5) cout << get_prev(root, x) << endl;
        else cout << get_next(root, x) << endl;
    }
    return 0;
}
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
using namespace std;
const int N = 100001;
int n, op, x;
int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];
struct Splay {
    void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }
    bool get(int x) { return x == ch[fa[x]][1]; }
    void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0; }
    void rotate(int x) {
        int y = fa[x], z = fa[y], chk = get(x);
        ch[y][chk] = ch[x][chk ^ 1];
        if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
        ch[x][chk ^ 1] = y;
        fa[y] = x;
        fa[x] = z;
        if (z) ch[z][y == ch[z][1]] = x;
        maintain(x);
        maintain(y);
    }
    void splay(int x) {
        for (int f = fa[x]; f = fa[x], f; rotate(x))
            if (fa[f]) rotate(get(x) == get(f) ? f : x);
        rt = x;
    }
    void ins(int k) {
        if (!rt) {
            val[++tot] = k;
            cnt[tot]++;
            rt = tot;
            maintain(rt);
            return;
        }
        int cur = rt, f = 0;
        while (1) {
            if (val[cur] == k) {
                cnt[cur]++;
                maintain(cur);
                maintain(f);
                splay(cur);
                break;
            }
            f = cur;
            cur = ch[cur][val[cur] < k];
            if (!cur) {
                val[++tot] = k;
                cnt[tot]++;
                fa[tot] = f;
                ch[f][val[f] < k] = tot;
                maintain(tot);
                maintain(f);
                splay(tot);
                break;
            }
        }
    }
    int rk(int k) {
        int res = 0, cur = rt;
        while (1) {
            if (k < val[cur]) cur = ch[cur][0];
            else {
                res += sz[ch[cur][0]];
                if (k == val[cur]) {
                    splay(cur);
                    return res + 1;
                }
                res += cnt[cur];
                cur = ch[cur][1];
            }
        }
    }
    int kth(int k) {
        int cur = rt;
        while (1) {
            if (ch[cur][0] && k <= sz[ch[cur][0]]) {
                cur = ch[cur][0];
            } else {
                k -= cnt[cur] + sz[ch[cur][0]];
                if (k <= 0) {
                    splay(cur);
                    return val[cur];
                }
                cur = ch[cur][1];
            }
        }
    }
    int pre() {
        int cur = ch[rt][0];
        if (!cur) return cur;
        while (ch[cur][1]) cur = ch[cur][1];
        splay(cur);
        return cur;
    }
    int nxt() {
        int cur = ch[rt][1];
        if (!cur) return cur;
        while (ch[cur][0]) cur = ch[cur][0];
        splay(cur);
        return cur;
    }
    void del(int k) {
        rk(k);
        if (cnt[rt] > 1) {
            cnt[rt]--;
            maintain(rt);
            return;
        }
        if (!ch[rt][0] && !ch[rt][1]) {
            clear(rt);
            rt = 0;
            return;
        }
        if (!ch[rt][0]) {
            int cur = rt;
            rt = ch[rt][1];
            fa[rt] = 0;
            clear(cur);
            return;
        }
        if (!ch[rt][1]) {
            int cur = rt;
            rt = ch[rt][0];
            fa[rt] = 0;
            clear(cur);
            return;
        }
        int cur = rt;
        int x = pre();
        fa[ch[cur][1]] = x;
        ch[x][1] = ch[cur][1];
        clear(cur);
        maintain(rt);
    }
} tree;
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    while (n--) {
        cin >> op >> x;
        if (op == 1) tree.ins(x);
        else if (op == 2) tree.del(x);
        else if (op == 3) cout << tree.rk(x) << endl;
        else if (op == 4) cout << tree.kth(x) << endl;
        else if (op == 5) tree.ins(x), cout << val[tree.pre()] << endl, tree.del(x);
        else tree.ins(x), cout << val[tree.nxt()] << endl, tree.del(x);
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size(), i = 0;
        vector<int> ans(n, 0);
        for (auto &p : positions) {
            int l = p[0], h = p[1], r = l + h - 1;
            ans[i] = h;
            for (int j = 0; j < i; ++j)
                if (r >= positions[j][0] && l <= (positions[j][0] + positions[j][1] - 1))
                    ans[i] = max(ans[i], ans[j] + h);
            ++i;
        }
        for(i = 1; i < n; ++i)
            ans[i] = max(ans[i], ans[i - 1]);
        return ans;
    }
};
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
class Solution {
public:
    const int N = 1e9;
    struct Node {
        int val, add;
        Node *ls, *rs;
    };
    Node *root;
    void pushdown(Node *node) {
        if (!node->ls) node->ls = new Node();
        if (!node->rs) node->rs = new Node();
        if (node->add == 0) return;
        node->ls->add = node->ls->val = node->add;
        node->rs->add = node->rs->val = node->add;
        node->add = 0;
    }
    void pushup(Node *node) {
        node->val = max(node->ls->val, node->rs->val);
    }
    int query(Node *node, int l, int r, int L, int R) {
        if (L <= l && r <= R) return node->val;
        pushdown(node);
        int mid = (l + r) >> 1, ans = 0;
        if (L <= mid) ans = query(node->ls, l, mid, L, R);
        if (R > mid) ans = max(ans, query(node->rs, mid + 1, r, L, R));
        return ans;
    }
    void update(Node *node, int l, int r, int L, int R, int v) {
        if (L <= l && r <= R) node->add = node->val = v;
        else {
            pushdown(node);
            int mid = (l + r) >> 1;
            if (L <= mid) update(node->ls, l, mid, L, R, v);
            if (R > mid) update(node->rs, mid + 1, r, L, R, v);
            pushup(node);
        }
    }
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> ans(positions.size());
        root = new Node();
        int i = 0;
        for (auto &p : positions) {
            int l = p[0], h = p[1], r = l + h - 1;
            int curr = query(root, 0, N, l, r);
            update(root, 0, N, l, r, curr + h);
            ans[i++] = root->val;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    map<int, int> m; // [l, h], start from l, the height is h, until the next point.
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size(), i = 0;
        vector<int> ans(n);
        m[0] = 0;
        for (auto &p : positions) {
            int l = p[0], h = p[1], r = l + h - 1;
            auto lp = m.upper_bound(l), rp = m.upper_bound(r);
            int ph = prev(rp)->second;
            int piledHeight = 0;
            for (auto p = prev(lp); p != rp; ++p)
                piledHeight = max(piledHeight, p->second + h);
            m.erase(lp, rp);
            m[l] = piledHeight;
            if (rp == m.end() || rp->first != r + 1)
                m[r + 1] = ph;
            ans[i] = i ? max(ans[i - 1], piledHeight) : h;
            ++i;
        }
        return ans;
    }
};

Posted on Edited on In 
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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 100001;
const LL INF = 1e15;
const double EPS = 1e-5;
int n, m, op, x, a[N];
LL val;
vector<double> nums;
struct Node {
    int l, r, cnt;
    LL sum;
} tr[N << 3];
struct Q {
    int op, x;
    LL val;
} ques[N];
int find(int x) {
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
void pushup(int u) {
    tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
pair<int, LL> query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return {tr[u].cnt, tr[u].sum};
    int c = 0, mid = (tr[u].l + tr[u].r) >> 1;
    LL s = 0;
    if (l <= mid) {
        auto [cnt, sum] = query(u << 1, l, r);
        c = cnt, s = sum;
    }
    if (r > mid) {
        auto [cnt, sum] = query(u << 1 | 1, l, r);
        c += cnt, s += sum;
    }
    return {c, s};
}
void solve(LL x) {
    double l = 0, r = INF, res = 0;
    while (r - l >= EPS) {
        double mid = (l + r) / 2;
        int p = upper_bound(nums.begin(), nums.end(), mid) - nums.begin();
        auto [cnt, sum] = query(1, 1, p);
        if (cnt * mid >= sum + x) r = res = mid;
        else l = mid;
    }
    printf("%.5f\n", res);
}
void modify(int u, int x, int k) {
    if (tr[u].l == tr[u].r) {
        tr[u].cnt += k, tr[u].sum += (nums[x - 1] * k);
    } else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) modify(u << 1, x, k);
        else modify(u << 1 | 1, x, k);
        pushup(u);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), nums.push_back(a[i]);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%lld", &x, &val);
            ques[i] = {1, x, val};
            nums.push_back(val);
        } else {
            scanf("%lld", &val);
            ques[i] = {0, 0, val};
        }
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    build(1, 1, nums.size());
    for (int i = 1; i <= n; ++i) modify(1, find(a[i]) + 1, 1);
    for (int i = 1; i <= m; ++i) {
        auto &[op, x, val] = ques[i];
        if (op == 1) {
            modify(1, find(a[x]) + 1, -1);
            a[x] = val;
            modify(1, find(a[x]) + 1, 1);
        } else solve(val);
    }
    return 0;
}
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
#include <cstdio>
#include <utility>
using namespace std;
using LL = long long;
const int N = 100001;
const LL INF = 1e15;
const double EPS = 1e-5;
int n, m, op, x, a[N], mx = 1e9 + 10, idx = 1;
LL val;
struct Node {
    int l, r, cnt;
    LL sum;
} tr[N * 100];
void pushup(int u) {
    tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}
pair<int, LL> query(int u, int l, int r, double L, double R) {
    if (L <= l && r <= R) return {tr[u].cnt, tr[u].sum};
    int c = 0, mid = (l + r) >> 1;
    LL s = 0;
    if (L <= mid && tr[u].l) {
        auto [cnt, sum] = query(tr[u].l, l, mid, L, R);
        c = cnt, s = sum;
    }
    if (R > mid && tr[u].r) {
        auto [cnt, sum] = query(tr[u].r, mid + 1, r, L, R);
        c += cnt, s += sum;
    }
    return {c, s};
}
void solve(LL x) {
    double l = 0, r = INF;
    while (r - l >= EPS) {
        double mid = (l + r) / 2;
        if (mid >= mx) {
            if (tr[1].cnt * mid >= tr[1].sum + x) r = mid;
            else l = mid;
        } else {
            auto [cnt, sum] = query(1, 0, mx, 0, mid);
            if (cnt * mid >= sum + x) r = mid;
            else l = mid;
        }
    }
    printf("%.5f\n", l);
}
void modify(int u, int l, int r, int x, int k) {
    if (l == r) {
        tr[u].cnt += k, tr[u].sum += x * k;
    } else {
        int mid = (l + r) >> 1;
        if (x <= mid) {
            if (!tr[u].l) tr[u].l = ++idx;
            modify(tr[u].l, l, mid, x, k);
        } else {
            if (!tr[u].r) tr[u].r = ++idx;
            modify(tr[u].r, mid + 1, r, x, k);
        }
        pushup(u);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), modify(1, 0, mx, a[i], 1);
    while (m--) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%lld", &x, &val);
            modify(1, 0, mx, a[x], -1);
            a[x] = val;
            modify(1, 0, mx, a[x], 1);
        } else {
            scanf("%lld", &val);
            solve(val);
        }
    }
    return 0;
}

Posted on Edited on In 
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
#include <iostream>
using namespace std;
using LL = long long;
const int N = 500000;
int n, q[N], tmp[N];
LL merge_sort(int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    LL ans = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> q[i];
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}
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
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 500001;
int n, a[N], b[N];
LL ans;
struct Node {
    int l, r, v;
} tr[N << 2];
void pushup(int u) {
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
void build(int u, int l, int r) {
    tr[u] = {l, r, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void update(int u, int pos) {
    if (tr[u].l == tr[u].r) ++tr[u].v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (pos <= mid) update(u << 1, pos);
        else update(u << 1 | 1, pos);
        pushup(u);
    }
}
int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int ret = 0;
    if (l <= mid) ret = query(u << 1, l, r);
    if (r > mid) ret += query(u << 1 | 1, l, r);
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = a[i];
    build(1, 1, n);
    sort(b + 1, b + n + 1);
    int len = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) {
        int pos = lower_bound(b + 1, b + len + 1, a[i]) - b;
        if (pos != n) ans += query(1, pos + 1, n);
        update(1, pos);
    }
    cout << ans << endl;
    return 0;
}
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
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 500001;
int n, a[N], b[N], t[N];
LL ans;
int lowbit(int x) {
    return x & -x;
}
int add(int x) {
    while (x <= n) {
        ++t[x];
        x += lowbit(x);
    }
}
int sum(int x) {
    int ret = 0;
    while (x) {
        ret += t[x];
        x -= lowbit(x);
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = i;
    sort(b + 1, b + n + 1, [&](int x, int y) {
        return a[x] == a[y] ? x > y : a[x] > a[y];
    });
    for (int i = 1; i <= n; ++i) {
        add(b[i]);
        ans += sum(b[i] - 1);
    }
    cout << ans << endl;
    return 0;
}
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
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
using LL = long long;
const int N = 500000;
struct Node {
    int val, fix;
    int cnt, siz;
    Node *ls, *rs;
    Node(int v) {
        val = v, fix = rand();
        ls = rs = nullptr;
        siz = cnt = 1;
    }
};
int n, s;
LL ans;
Node *root;
int siz(Node *&k) {
    return k ? k->siz : 0;
}
void pushup(Node *&k) {
    k->siz = siz(k->ls) + siz(k->rs) + k->cnt;
}
void zag(Node *&k2) {
    Node *k1 = k2->rs;
    k2->rs = k1->ls;
    k1->ls = k2;
    pushup(k2), pushup(k1);
    k2 = k1;
}
void zig(Node *&k2) { 
    Node *k1 = k2->ls;
    k2->ls = k1->rs;
    k1->rs = k2;
    pushup(k2), pushup(k1);
    k2 = k1;
}
void insert(Node *&node, int x) {
    if (!node) node = new Node(x);
    else if (x < node->val) {
        insert(node->ls, x);
        if (node->ls->fix < node->fix) zig(node);
        else ++node->siz;
    } else if (x > node->val) {
        insert(node->rs, x);
        if (node->rs->fix < node->fix) zag(node);
        else ++node->siz;
    } else ++node->cnt, ++node->siz;
}
int query(int x) { 
    int ret = 0;
    Node *node = root;
    while (node && node->val ^ x)
        if (node->val < x) node = node->rs;
        else { 
            ret += siz(node->rs) + node->cnt;
            node = node->ls;
        }
    if (node && node->val == x) return ret + siz(node->rs);
    else return ret;
}
int main() {
    ios::sync_with_stdio(false);
    srand(time(nullptr));
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        ans += query(s);
        insert(root, s);
    }
    cout << ans << endl;
    return 0;
}
0%