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

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
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
struct Node {
    int l, r;
    mutable int v;
    Node(int l, int r, int v) : l(l), r(r), v(v) {}
    bool operator <(const Node &o) const {
        return l < o.l;
    }
};
int n, q, s;
set<Node> tree;
set<Node>::iterator split(int pos) {
    auto it = tree.lower_bound({pos, 0, 0});
    if (it != tree.end() && it->l == pos)
        return it;
    --it;
    auto [l, r, v] = *it;
    tree.erase(it);
    tree.insert({l, pos - 1, v});
    return tree.insert({pos, r, v}).first;
}
void assign(int l, int r, int v) {
    auto end = split(r + 1), begin = split(l);
    int tot = 0, len = 0;
    for (auto it = begin; it != end; ++it) {
        len += (it->r - it->l + 1);
        tot += it->v * (it->r - it->l + 1);
    }
    tree.erase(begin, end);
    tree.insert({l, r, v});
    if (v) s += (len - tot);
    else s -= tot;
}
int main(void) {
    scanf("%d%d", &n, &q);
    tree.insert({1, n, 1});
    s = n;
    while (q--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        assign(l, r, k != 1);
        printf("%d\n", s);
    }
    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
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
struct Node {
    LL l, r;
    mutable LL v;
    Node(LL l, LL r, LL v) : l(l), r(r), v(v) {}
    bool operator <(const Node &o) const {
        return l < o.l;
    }
};
LL n, m, seed, vmax;
set<Node> tree;
LL rnd() {
    LL ans = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ans;
}
LL qpow(LL a, LL k, LL p) {
    LL ans = 1;
    a %= p;
    while (k) {
        if (k & 1)
            ans = ans * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return ans;
}
// if pos isn't a range start, then split its range from pos into [l, pos - 1], [pos, r].
set<Node>::iterator split(LL pos) {
    auto it = tree.lower_bound({pos, 0, 0});
    if (it != tree.end() && it->l == pos)
        return it;
    --it;
    auto [l, r, v] = *it;
    tree.erase(it);
    tree.insert({l, pos - 1, v});
    return tree.insert({pos, r, v}).first;
}
void add(LL l, LL r, LL v) {
    auto end = split(r + 1);
    for (auto it = split(l); it != end; ++it)
        it->v += v;
}
void assign(LL l, LL r, LL v) {
    auto end = split(r + 1), begin = split(l);
    tree.erase(begin, end);
    tree.insert({l, r, v});
}
LL kth(LL l, LL r, LL k) {
    auto end = split(r + 1);
    vector<pair<LL, LL>> v;
    for (auto it = split(l); it != end; ++it)
        v.emplace_back(it->v, it->r - it->l + 1);
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); ++i) {
        k -= v[i].second;
        if (k <= 0)
            return v[i].first;
    }
}
LL sumOfPow(LL l, LL r, LL x, LL y) {
    LL tot = 0;
    auto end = split(r + 1);
    for (auto it = split(l); it != end; ++it)
        tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y;
    return tot;
}
int main(void) {
    scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);
    for (int i = 1; i <= n; ++i) {
        int r = rnd();
        tree.insert({i, i, r % vmax + 1});
    }
    for (int i = 1; i <= m; ++i) {
        LL op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1, x, y;
        if (l > r) swap(l, r);
        if (op == 3) x = rnd() % (r - l + 1) + 1;
        else x = rnd() % vmax + 1;
        if (op == 4) y = rnd() % vmax + 1;
        switch (op) {
            case 1:
                add(l, r, x);
                break;
            case 2:
                assign(l, r, x);
                break;
            case 3:
                printf("%lld\n", kth(l, r, x));
                break;
            case 4:
                printf("%lld\n", sumOfPow(l, r, x ,y));
        }
    }
    return 0;
}
0%