Shawn's Blog

CodeForces 1691E Number of Groups

Posted on 2022-06-02 Edited on 2024-03-13 In CodeForces

#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;
}

AcWing 4340. 我讨厌它

Posted on 2022-06-02 Edited on 2024-03-13 In AcWing

原题为 HDU 1754 I Hate It。

#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;
}

#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;
}

#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;
}

POJ 3264 Balanced Lineup

Posted on 2022-06-01 Edited on 2024-03-13 In POJ

#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;
}

#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;
}

#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;
}

CodeForces 522D Closest Equals

Posted on 2022-06-01 Edited on 2024-03-13 In CodeForces

// 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]);
}

洛谷 P3834 【模板】可持久化线段树 2

Posted on 2022-06-01 Edited on 2024-03-13 In 洛谷

#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;
}

洛谷 P3369 【模板】普通平衡树

Posted on 2022-05-31 Edited on 2024-03-13 In 洛谷

Treap
Splay

#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;
}

#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;
}

LeetCode 699. Falling Squares

Posted on 2022-05-30 Edited on 2024-03-13 In LeetCode

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;
    }
};

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;
    }
};

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;
    }
};

CodeForces 431E Chemistry Experiment

Posted on 2022-05-30 Edited on 2024-03-13 In CodeForces

线段树
线段树(动态开点)

#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;
}

#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;
}

洛谷 P1908 逆序对

Posted on 2022-05-28 Edited on 2024-03-13 In 洛谷

#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;
}

#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;
}

#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;
}

#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;
}

pintia The 2021 ICPC Asia Regionals Online Contest (II) L Euler Function

Posted on 2022-05-27 Edited on 2024-03-13 In pintia

ProblemSet Problem - L Euler Function

Given as a prime,

we have when is a fator of ;
otherwise, we have .