Shawn's Blog

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

Posted 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
#include <cstdio>
using namespace std;
using LL = long long;
const int N = 100001;
int n, p, m, op, l, r, d, w[N];
struct Node {
    int l, r, sum, mul, add;
} tr[N << 2];
void eval(Node &t, LL mul, LL add) {
    t.sum = (t.sum * mul + (t.r - t.l + 1) * add) % p;
    t.mul = (t.mul * mul) % p;
    t.add = (t.add * mul + add) % p;
}
void pushup(int u) {
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}
void pushdown(int u) {
    if (tr[u].mul == 1 && tr[u].add == 0) return;
    eval(tr[u << 1], tr[u].mul, tr[u].add);
    eval(tr[u << 1 | 1], tr[u].mul, tr[u].add);
    tr[u].mul = 1, tr[u].add = 0;
}
void build(int u, int l, int r) {
    if (l == r) tr[u] = {l, r, w[l], 0, 0};
    else {
        tr[u] = {l, r, 0, 1, 0};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void update(int u, int l, int r, int mul, int add) {
    if (l <= tr[u].l && tr[u].r <= r) eval(tr[u], mul, add);
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, mul, add);
        if (r > mid) update(u << 1 | 1, l, r, mul, add);
        pushup(u);
    }
}
int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
    return sum;
}
int main() {
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    build(1, 1, n);
    while (m--) {
        scanf("%d%d%d", &op, &l, &r);
        if (op == 3) {
            printf("%d\n", query(1, l, r));
        } else {
            scanf("%d", &d);
            if (op == 1) update(1, l, r, d, 0);
            else update(1, l, r, 1, d);
        }
    }
    return 0;
}

Posted 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
#include <iostream>
using namespace std;
using LL = long long;
const int N = 100001;
int n, m, t, l, r, x, a[N];
struct Node {
    int l, r, maxn;
    LL sum;
} tr[N << 2];
void pushup(int u) {
    tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        tr[u].sum = a[l], tr[u].maxn = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int l, int r, int x) {
    if (tr[u].maxn < x) return;
    if (tr[u].l == tr[u].r) {
        tr[u].maxn %= x, tr[u].sum = tr[u].maxn;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, x);
    if (r > mid) modify(u << 1 | 1, l, r, x);
    pushup(u);
}
void modify(int u, int k, int v) {
    if (tr[u].l == tr[u].r) {
        tr[u].maxn = tr[u].sum = v;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (k <= mid) modify(u << 1, k, v);
    else modify(u << 1 | 1, k, v);
    pushup(u);
}
LL query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    LL ans = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) ans = query(u << 1, l, r);
    if (r > mid) ans += query(u << 1 | 1, l, r);
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
        scanf("%d", &t);
        if (t == 1) {
            scanf("%d%d", &l, &r);
            printf("%lld\n", query(1, l, r));
        } else if (t == 2) {
            scanf("%d%d%d", &l, &r, &x);
            modify(1, l, r, x);
        } else {
            scanf("%d%d", &l, &x);
            modify(1, l, x);
        }
    }
    return 0;
}

Posted 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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 101;
int n, k, tot;
double ans, x1, y1, x2, y2;
struct Line {
    double x, y1, y2;
    int d;
    bool operator < (const Line &o) const {
        return x < o.x; // scan from left to right.
    }
} line[N << 1];
struct Node {
    int l, r, cnt; // left, right, count of covered times.
    double len; // length/height of covered range.
} tr[N << 3];
double ys[N << 1];
int get(double x) {
    return lower_bound(ys + 1, ys + 1 + tot, x) - ys;
}
// pushup to the root to make sure len is maintained properly.
void pushup(int u) {
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l != tr[u].r) {
        // (u << 1) when tr[u].t == tr[u].r (leaf node) could cause segfault.
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    } else tr[u].len = 0;
}
// no need to pushup on building coz all cnt/len is 0.
void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l != r) {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}
// the query is against the whole tree every time,
// and update for every single range is paired and comes with +d first, -d next.
// so no need to push down.
void update(int u, int l, int r, int d) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].cnt += d;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
    }
    pushup(u);
}
int main() {
    while (scanf("%d", &n), n) {
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            line[i] = {x1, y1, y2, 1}, line[i + n] = {x2, y1, y2, -1};
            ys[i] = y1, ys[i + n] = y2;
        }
        n *= 2; // for convenience.
        sort(ys + 1, ys + 1 + n);
        tot = unique(ys + 1, ys + 1 + n) - ys - 1;
        build(1, 1, tot - 1);
        sort(line + 1, line + 1 + n);
        update(1, get(line[1].y1), get(line[1].y2) - 1, line[1].d);
        for (int i = 2; i <= n; ++i) {
            ans += tr[1].len * (line[i].x - line[i - 1].x);
            update(1, get(line[i].y1), get(line[i].y2) - 1, line[i].d);
        }
        printf("Test case #%d\n", ++k);
        printf("Total explored area: %.2f\n\n", ans);
    }
    return 0;
}

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans = {1};
        while (ans.size() < n) {
            vector<int> tmp;
            for (int i : ans) if (i * 2 - 1 <= n) tmp.push_back(i * 2 - 1);
            for (int i : ans) if (i * 2 <= n) tmp.push_back(i * 2);
            ans = tmp;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    unordered_map<int, vector<int>> m;
    vector<int> beautifulArray(int n) {
        if (m.count(n)) return m[n];
        vector<int> ans(n);
        if (n == 1) ans[0] = 1;
        else {
            int i = 0;
            for (int x : beautifulArray((n + 1) / 2)) // odds.
                ans[i++] = 2 * x - 1;
            for (int x : beautifulArray(n / 2)) // evens.
                ans[i++] = 2 * x;
        }
        m[n] = ans;
        return ans;
    }
};

Reference: Odd + Even Pattern, O(N) - LeetCode Discuss

Posted 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
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int t, n, m, i, j, p[N << 1];
bool valid, vis[N << 1];
char c[9];
vector<int> g[N << 1];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y) {
    p[find(x)] = find(y);
}
// calculate the cnt (s1, s2) of vertex of each disjoint set in a bipartite graph.
void dfs(int u, int &s1, int &s2) {
    vis[u] = true;
    if (u <= n) ++s1;
    else ++s2;
    for (int v : g[u])
        if (!vis[v])
            dfs(v, s1, s2);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n << 1; ++i) {
            p[i] = i, vis[i] = false;
            g[i].clear();
        }
        while (m--) {
            scanf("%d%d%s", &i, &j, c);
            if (*c == 'i') {
                merge(i + n, j);
                merge(i, j + n);
                g[i].emplace_back(j + n);
                g[i + n].emplace_back(j);
                g[j].emplace_back(i + n);
                g[j + n].emplace_back(i);
            } else {
                merge(i, j);
                merge(i + n, j + n);
                g[i].emplace_back(j);
                g[j].emplace_back(i);
                g[i + n].emplace_back(j + n);
                g[j + n].emplace_back(i + n);
            }
        }
        valid = true;
        for (int i = 1; i <= n; ++i)
            if (find(i) == find(i + n)) {
                valid = false;
                break;
            }
        if (!valid) printf("-1\n");
        else {
            int ans = 0;
            for (int i = 1, s1 = 0, s2 = 0; i <= n; ++i)
                if (!vis[i] && !vis[i + n])
                    s1 = 0, s2 = 0, dfs(i, s1, s2), ans += max(s1, s2);
            printf("%d\n", ans);
        }
    }
    return 0;
}

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minInsertions(string s) {
        // c is used to track the diff between the cnt of '(' and '))'.
        int n = s.size(), c = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                ++c; // c should remain nonnegative.
            } else {
                // if there is no one more ')' available, we need to insert a ')'.
                if (i >= n - 1 || s[i + 1] != ')') ++ans;
                // or, consume it.
                else ++i;
                // if there is no enough preceding '(' to match this '))' group, we need to insert a '('.
                if (c <= 0) ++ans, c = 0;
                // or, consume the preceding '('.
                else --c;
            }
        }
        return ans + c * 2;
    }
};

Posted 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
class Solution {
public:
    int maximumGood(vector<vector<int>>& statements) {
        int n = statements.size(), ans = 0;
        vector<int> gg(n), bb(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (statements[i][j] == 0) {
                    bb[i] |= (1 << j);
                } else if (statements[i][j] == 1) {
                    gg[i] |= (1 << j);
                }
            }
        }
        function<void(int, int, int)> dfs = [&](int g, int b, int i) {
            if (g & b) return; // conflict.
            if (i == n) {
                ans = max(ans, __builtin_popcount(g));
                return;
            }
            if (n - __builtin_popcount(b) < ans) return; // pruning.
            // 1. say i is good.
            dfs(g | (1 << i) | gg[i], b | bb[i], i + 1);
            // 2. say i is bad.
            dfs(g, b | (1 << i), i + 1);
        };
        dfs(0, 0, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maximumGood(vector<vector<int>> &statements) {
        int n = statements.size(), ans = 0;
        for (int i = 1; i < 1 << n; ++i) { // enumerate each case represented by a bit mask.
            int cnt = 0, valid = true;
            for (int j = 0; j < n && valid; ++j) {
                if ((i >> j) & 1) { // if j is good.
                    for (int k = 0; k < n && valid; ++k) { // check if there is conflict.
                        if (statements[j][k] < 2 && statements[j][k] != ((i >> k) & 1)) {
                            valid = false;
                        }
                    }
                    cnt += valid;
                }
            }
            if (valid) ans = max(ans, cnt);
        }
        return ans;
    }
};

Posted 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
#include <iostream>
using namespace std;
const int N = 5e5 + 10, INF = -5e8 - 10;
int n, m, k, a, b;
struct Node {
    int l, r;
    int lmax, rmax, sum, tmax;
} tr[N << 2];
void pushup(Node &rt, Node &left, Node &right) {
    rt.tmax = max(left.rmax + right.lmax, max(left.tmax, right.tmax));
    rt.lmax = max(left.lmax, left.sum + right.lmax);
    rt.rmax = max(right.rmax, left.rmax + right.sum);
    rt.sum = left.sum + right.sum;
}
void pushup(int u) {
    auto &rt = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    pushup(rt, left, right);
}
void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        scanf("%d", &a);
        tr[u].lmax = tr[u].rmax = tr[u].sum = tr[u].tmax = a;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
Node query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    if (l > mid) return query(u << 1 | 1, l, r);
    Node ans, ln = query(u << 1, l, r), rn = query(u << 1 | 1, l, r);
    pushup(ans, ln, rn);
    return ans;
}
void update(int u, int i, int v) {
    if (tr[u].l == i && tr[u].r == i) {
        tr[u].lmax = tr[u].rmax = tr[u].sum = tr[u].tmax = v;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (i <= mid) update(u << 1, i, v);
    else update(u << 1 | 1, i, v);
    pushup(u);
}
int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m--) {
        scanf("%d%d%d", &k, &a, &b);
        if (k == 1) {
            if (a > b) swap(a, b);
            printf("%d\n", query(1, a, b).tmax);
        } else {
            update(1, a, b);
        }
    }
    return 0;
}
0%