kuangbin 专题七 线段树

Posted on Edited on In

题目详单见 [kuangbin带你飞]专题1-23。
算法介绍见 线段树 - OI Wiki。

HDU-1166 敌兵布阵

线段树求区间和模板题，单点更新，区间求和。也可以用树状数组。

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 <iostream>
#define lc p << 1
#define rc p << 1 | 1
#define N 50001
using namespace std;
int t, n, w[N], val[N << 2], hold[N << 2]; // 虽然这题不需要懒标记。
void build(int p, int s, int t)
{
    val[p] = w[s], hold[p] = 0;
    if (s == t)
        return;
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
void update(int l, int r, int c, int p, int s, int t) // 虽然这题是单点更新。
{
    if (l <= s && t <= r)
    {
        val[p] += (t - s + 1) * c;
        hold[p] += c;
        return;
    }
    int m = t + s >> 1;
    if (hold[p] && s != t)
    {
        val[lc] += hold[p] * (m - s + 1);
        val[rc] += hold[p] * (t - m);
        hold[lc] += hold[p];
        hold[rc] += hold[p];
        hold[p] = 0;
    }
    if (l <= m)
        update(l, r, c, lc, s, m);
    if (r > m)
        update(l, r, c, rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
int query(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
        return val[p];
    int m = s + t >> 1;
    if (hold[p])
    {
        val[lc] += hold[p] * (m - s + 1);
        val[rc] += hold[p] * (t - m);
        hold[lc] += hold[p];
        hold[rc] += hold[p];
        hold[p] = 0;
    }
    int res = 0;
    if (l <= m)
        res += query(l, r, lc, s, m);
    if (r > m)
        res += query(l, r, rc, m + 1, t);
    return res;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> w[i];
        build(1, 1, n);
        cout << "Case " << _ << ":" << endl;
        while (1)
        {
            string op;
            int i, j;
            cin >> op;
            if (op[0] == 'Q') // Query.
            {
                cin >> i >> j;
                cout << query(i, j, 1, 1, n) << endl;
            }
            else if (op[0] == 'A') // Add.
            {
                cin >> i >> j;
                update(i, i, j, 1, 1, n);
            }
            else if (op[0] == 'S') // Sub.
            {
                cin >> i >> j;
                update(i, i, -j, 1, 1, n);
            }
            else
                break;
        }
    }
    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
#include <iostream>
#define lowbit(x) (x & -x)
#define N 50001
using namespace std;
int t, n, tr[N];
void update(int i, int k)
{
    for (; i <= n; i += lowbit(i))
        tr[i] += k;
}
int query(int i)
{
    int s = 0;
    for (; i > 0; i -= lowbit(i))
        s += tr[i];
    return s;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            tr[i] = 0;
        for (int i = 1, x; i <= n; ++i)
        {
            cin >> x;
            // update(i, x);
            tr[i] += x;
            int j = i + lowbit(i);
            if (j <= n)
                tr[j] += tr[i];
        }
        cout << "Case " << _ << ":" << endl;
        while (1)
        {
            string op;
            int i, j;
            cin >> op;
            if (op[0] == 'Q') // Query.
            {
                cin >> i >> j;
                cout << query(j) - query(i - 1) << endl;
            }
            else if (op[0] == 'A') // Add.
            {
                cin >> i >> j;
                update(i, j);
            }
            else if (op[0] == 'S') // Sub.
            {
                cin >> i >> j;
                update(i, -j);
            }
            else
                break;
        }
    }
    return 0;
}

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
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 <iostream>
#include <algorithm>
#define lc p << 1
#define rc p << 1 | 1
#define N 200001
using namespace std;
int n, m, w[N];
int val[N << 2];
void build(int p, int s, int t)
{
    if (s == t)
    {
        val[p] = w[s];
        return;
    }
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
    val[p] = max(val[lc], val[rc]);
}
void update(int x, int c, int p, int s, int t)
{
    if (s == x && x == t)
    {
        val[p] = c;
        return;
    }
    int m = s + t >> 1;
    if (x <= m)
        update(x, c, lc, s, m);
    else
        update(x, c, rc, m + 1, t);
    val[p] = max(val[lc], val[rc]);
}
int query(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
        return val[p];
    int m = s + t >> 1;
    int res = 0;
    if (l <= m)
        res = max(res, query(l, r, lc, s, m));
    if (r > m)
        res = max(res, query(l, r, rc, m + 1, t));
    return res;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; ++i)
            cin >> w[i];
        build(1, 1, n);
        string op;
        int i, j;
        while (m--)
        {
            cin >> op >> i >> j;
            if (op[0] == 'Q')
                cout << query(i, j, 1, 1, n) << endl;
            else
                update(i, j, 1, 1, n);
        }
    }
    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
#include <iostream>
#include <algorithm>
#define lowbit(x) (x & -x)
#define N 200001
using namespace std;
int n, m, w[N], tr[N];
void update(int i)
{
    for (; i <= n; i += lowbit(i))
    {
        tr[i] = w[i];
        int l = lowbit(i);
        for (int j = 1; j < l; 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()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; ++i)
            tr[i] = 0;
        for (int i = 1, x; i <= n; ++i)
        {
            cin >> w[i];
            update(i);
        }
        string op;
        int i, j;
        while (m--)
        {
            cin >> op >> i >> j;
            if (op[0] == 'Q')
                cout << query(i, j) << endl;
            else
                w[i] = j, update(i);
        }
    }
    return 0;
}

POJ-3468 A Simple Problem with Integers

线段树维护区间和，区间更新，区间查询。使用懒标记可以降低平均复杂度。

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 <iostream>
#define lc p << 1
#define rc p << 1 | 1
#define N 100001
#define ll long long
using namespace std;
int n, q, w[N];
ll val[N << 2], hold[N << 2];
void build(int p, int s, int t)
{
    val[p] = w[s], hold[p] = 0;
    if (s == t)
        return;
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
void pushdown(int p, int s, int t)
{
    if (hold[p])
    {
        int m = s + t >> 1;
        val[lc] += hold[p] * (m - s + 1);
        val[rc] += hold[p] * (t - m);
        hold[lc] += hold[p];
        hold[rc] += hold[p];
        hold[p] = 0;
    }
}
void update(int l, int r, int c, int p, int s, int t)
{
    if (l <= s && t <= r)
    {
        val[p] += (t - s + 1) * c;
        hold[p] += c;
        return;
    }
    int m = t + s >> 1;
    pushdown(p, s, t);
    if (l <= m)
        update(l, r, c, lc, s, m);
    if (r > m)
        update(l, r, c, rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
ll query(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
        return val[p];
    int m = s + t >> 1;
    pushdown(p, s, t);
    ll res = 0;
    if (l <= m)
        res += query(l, r, lc, s, m);
    if (r > m)
        res += query(l, r, rc, m + 1, t);
    return res;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> w[i];
    build(1, 1, n);
    string op;
    int l, r, c;
    while (q--)
    {
        cin >> op >> l >> r;

        if (op[0] == 'Q')
            cout << query(l, r, 1, 1, n) << endl;
        else
            cin >> c, update(l, r, c, 1, 1, n);
    }
    return 0;
}

POJ-2528 Mayor’s posters

// TODO

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
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#define lc p << 1
#define rc p << 1 | 1
#define N 10000
using namespace std;
int t, n;
pair<int, int> pos[N];
vector<int> s;
bool val[N << 3]; // covered.
int get(int x)
{
    return lower_bound(s.begin(), s.end(), x) - s.begin();
}
void build(int p, int s, int t)
{
    val[p] = 0;
    if (s == t)
        return;
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
}
bool update(int l, int r, int p, int s, int t)
{
    if (val[p])
        return 0;
    if (t == s)
        return val[p] = 1;
    bool res = 0;
    int m = s + t >> 1;
    if (l <= m)
        res |= update(l, r, lc, s, m);
    if (r > m)
        res |= update(l, r, rc, m + 1, t);
    if (val[lc] && val[rc]) // pushup.
        val[p] = 1;
    return res;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    while (t--)
    {
        s.clear();
        memset(val, 0, sizeof val);
        cin >> n;
        for (int i = 0, l, r; i < n; ++i)
        {
            cin >> l >> r;
            ++r;
            pos[i] = {l, r};
            s.push_back(l);
            s.push_back(r);
        }
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        int len = s.size() - 2;
        build(1, 0, len);
        int ans = 0;
        for (int i = n - 1, l, r; i >= 0; --i)
        {
            l = get(pos[i].first), r = get(pos[i].second) - 1;
            if (update(l, r, 1, 0, len))
                ++ans;
        }
        cout << ans << endl;
    }
    return 0;
}

HDU-1698 Just a Hook

线段树，区间更新，区间查询。

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
#include <iostream>
#define lc p << 1
#define rc p << 1 | 1
#define N 100001
using namespace std;
int t, n, q, val[N << 2], hold[N << 2];
void build(int p, int s, int t)
{
    val[p] = 1, hold[p] = 0;
    if (s == t)
        return;
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
void pushdown(int p, int s, int t)
{
    if (hold[p] && s != t)
    {
        int m = s + t >> 1;
        val[lc] = hold[p] * (m - s + 1);
        val[rc] = hold[p] * (t - m);
        hold[lc] = hold[p];
        hold[rc] = hold[p];
        hold[p] = 0;
    }
}
void update(int l, int r, int c, int p, int s, int t)
{
    if (l <= s && t <= r)
    {
        val[p] = (t - s + 1) * c;
        hold[p] = c;
        return;
    }
    pushdown(p, s, t);
    int m = s + t >> 1;
    if (l <= m)
        update(l, r, c, lc, s, m);
    if (r > m)
        update(l, r, c, rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
int query(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
        return val[p];
    pushdown(p, s, t);
    int m = s + t >> 1, res = 0;
    if (l <= m)
        res += query(l, r, lc, s, m);
    if (r > m)
        res += query(l, r, rc, m + 1, t);
    return res;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        cin >> n >> q;
        build(1, 1, n);
        int x, y, z;
        while (q--)
        {
            cin >> x >> y >> z;
            update(x, y, z, 1, 1, n);
        }
        cout << "Case " << _ << ": The total value of the hook is " << query(1, n, 1, 1, n) << "." << 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
#include <iostream>
#include <set>
using namespace std;
int t, n, q;
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;
    }
};
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);
    tree.erase(begin, end);
    tree.insert({l, r, v});
}
int query(int l, int r)
{
    auto end = split(r + 1), begin = split(l);
    int res = 0;
    for (auto it = begin; it != end; ++it)
        if (it->v != -1)
            res += it->v * (it->r - it->l + 1);
    return res;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        tree.clear();
        tree.insert({1, 1000000, 1});
        cin >> n >> q;
        int x, y, z;
        while (q--)
        {
            cin >> x >> y >> z;
            assign(x, y, z);
        }
        cout << "Case " << _ << ": The total value of the hook is " << query(1, n) << "." << endl;
    }
    return 0;
}

ZOJ-1610 Count the Colors

线段树，区间更新，区间查询。

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
#include <iostream>
#include <vector>
#include <map>
#define lc p << 1
#define rc p << 1 | 1
#define N 8000
using namespace std;
int n, val[(N + 1) << 2];
map<int, vector<int>> m;
void build(int p, int s, int t)
{
    val[p] = 0;
    if (s == t)
        return;
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
}
void pushdown(int p, int s, int t)
{
    if (val[p])
    {
        val[lc] = val[rc] = val[p];
        val[p] = 0;
    }
}
void update(int l, int r, int c, int p, int s, int t)
{
    if (l <= s && t <= r)
    {
        val[p] = c;
        return;
    }
    pushdown(p, s, t);
    int m = s + t >> 1;
    if (l <= m)
        update(l, r, c, lc, s, m);
    if (r > m)
        update(l, r, c, rc, m + 1, t);
}
void query(int l, int r, int p, int s, int t)
{
    if (s == t)
    {
        int c = val[p];
        if (c)
        {
            if (m[c].empty())
                m[c] = {t};
            else if (m[c].back() + 1 == s)
                m[c].back() = t;
            else
                m[c].push_back(t);
        }
        return;
    }
    pushdown(p, s, t);
    int m = s + t >> 1;
    if (l <= m)
        query(l, r, lc, s, m);
    if (r > m)
        query(l, r, rc, m + 1, t);
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    while (cin >> n)
    {
        build(1, 1, N);
        int l, r, c;
        while (n--)
        {
            cin >> l >> r >> c;
            update(l + 1, r, c + 1, 1, 1, N);
        }
        m.clear();
        query(1, N, 1, 1, N);
        for (auto &x : m)
            if (x.first != -1)
                cout << x.first - 1 << " " << x.second.size() << endl;
        cout << 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
#include <iostream>
#include <set>
#include <map>
using namespace std;
int n;
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;
    }
};
set<Node> tree;
auto 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);
    tree.erase(begin, end);
    tree.insert({l, r, v});
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    while (cin >> n)
    {
        tree.clear();
        tree.insert({0, 8000, -1});
        int l, r, c;
        while (n--)
        {
            cin >> l >> r >> c;
            assign(l, r - 1, c);
        }
        map<int, int> m;
        int pre = -1;
        for (auto &x : tree)
        {
            if (x.v != pre)
                m[x.v]++;
            pre = x.v;
        }
        for (auto &x : m)
            if (x.first != -1)
                cout << x.first << " " << x.second << endl;
        cout << endl;
    }
    return 0;
}

POJ-3264 Balanced Lineup

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
#include <cstdio>
#include <algorithm>
#define lc p << 1
#define rc p << 1 | 1
#define N 50001
using namespace std;
int n, q, w[N], min_val[N << 2], max_val[N << 2];
void build(int p, int s, int t)
{
    if (s == t)
    {
        min_val[p] = max_val[p] = w[s];
        return;
    }
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
    min_val[p] = min(min_val[lc], min_val[rc]);
    max_val[p] = max(max_val[lc], max_val[rc]);
}
pair<int, int> query(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
        return {min_val[p], max_val[p]};
    int m = s + t >> 1, min_val = 1e6, max_val = 1;
    if (l <= m)
    {
        pair<int, int> pa = query(l, r, lc, s, m);
        min_val = min(min_val, pa.first);
        max_val = max(max_val, pa.second);
    }
    if (r > m)
    {
        pair<int, int> pa = query(l, r, rc, m + 1, t);
        min_val = min(min_val, pa.first);
        max_val = max(max_val, pa.second);
    }
    return {min_val, max_val};
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
    build(1, 1, n);
    for (int i = 1, a, b; i <= q; ++i)
    {
        scanf("%d%d", &a, &b);
        pair<int, int> pa = query(a, b, 1, 1, n);
        printf("%d\n", pa.second - pa.first);
    }
    return 0;
}

HDU-4027 Can you answer these queries?

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
#include <iostream>
#include <cmath>
#define lc p << 1
#define rc p << 1 | 1
#define N 100001
#define ll long long
using namespace std;
int t, n, m;
ll val[N << 2];
void build(int p, int s, int t)
{
    if (s == t)
    {
        cin >> val[p];
        return;
    }
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
void update(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
    {
        if (val[p] <= t - s + 1)
            return;
    }
    if (s == t)
    {
        val[p] = sqrt(val[p]);
        return;
    }
    int m = s + t >> 1;
    if (l <= m)
        update(l, r, lc, s, m);
    if (r > m)
        update(l, r, rc, m + 1, t);
    val[p] = val[lc] + val[rc];
}
ll query(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
        return val[p];
    int m = s + t >> 1;
    ll res = 0;
    if (l <= m)
        res += query(l, r, lc, s, m);
    if (r > m)
        res += query(l, r, rc, m + 1, t);
    return res;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    while (cin >> n)
    {
        cout << "Case #" << ++t << ":" << endl;
        build(1, 1, n);
        cin >> m;
        for (int i = 0, t, x, y; i < m; ++i)
        {
            cin >> t >> x >> y;
            if (x > y)
                swap(x, y);
            if (t)
                cout << query(x, y, 1, 1, n) << endl;
            else
                update(x, y, 1, 1, n);
        }
    }
    return 0;
}

HDU-1540 Tunnel Warfare

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
#include <iostream>
#include <stack>
#define lc p << 1
#define rc p << 1 | 1
#define N 50001
using namespace std;
int n, m, len[N << 2], pre[N << 2], suf[N << 2];
stack<int> stk;
void pushup(int p, int s, int t)
{
    pre[p] = pre[lc];
    suf[p] = suf[rc];
    len[p] = max(max(len[lc], len[rc]), suf[lc] + pre[rc]);
    int m = s + t >> 1;
    if (len[lc] == m - s + 1)
        pre[p] += pre[rc];
    if (len[rc] == t - m)
        suf[p] += suf[lc];
}
void build(int p, int s, int t)
{
    len[p] = pre[p] = suf[p] = 1;
    if (s == t)
        return;
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
    pushup(p, s, t);
}
void update(int x, int c, int p, int s, int t)
{
    if (s == x && x == t)
    {
        len[p] = pre[p] = suf[p] = c;
        return;
    }
    int m = s + t >> 1;
    if (x <= m)
        update(x, c, lc, s, m);
    else
        update(x, c, rc, m + 1, t);
    pushup(p, s, t);
}
int query(int x, int p, int s, int t)
{
    if (s == t)
        return len[p];
    int m = s + t >> 1;
    if (x > m - suf[lc]      // x \in [m - suf[lc] + 1, ...].
        && x <= m + pre[rc]) // x \in [..., (m + 1) + pre[rc] - 1].
        return suf[lc] + pre[rc];
    return x <= m ? query(x, lc, s, m) : query(x, rc, m + 1, t);
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    while (cin >> n >> m)
    {
        build(1, 1, n);
        string op;
        int x;
        while (m--)
        {
            cin >> op;
            if (op[0] == 'D')
            {
                cin >> x;
                stk.push(x);
                update(x, 0, 1, 1, n);
            }
            else if (op[0] == 'R')
            {
                if (!stk.empty())
                {
                    x = stk.top();
                    stk.pop();
                    update(x, 1, 1, 1, n);
                }
            }
            else
            {
                cin >> x;
                cout << query(x, 1, 1, n) << endl;
            }
        }
    }
    return 0;
}

HDU-3974 Assign the task

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
#include <iostream>
#include <cstring>
#define lc p << 1
#define rc p << 1 | 1
#define N 50001
using namespace std;
int t, n, m, x, y;
string op;
int h[N], e[N], ne[N], idx, dfn[N], dfr[N], timestamp;
int val[N << 3];
bool hold[N << 3], isRoot[N];
void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void dfs(int u)
{
    dfn[u] = ++timestamp;
    for (int i = h[u]; ~i; i = ne[i])
        dfs(e[i]);
    dfr[u] = ++timestamp;
}
void build(int p, int s, int t)
{
    val[p] = -1, hold[p] = 0;
    if (s == t)
        return;
    int m = s + t >> 1;
    build(lc, s, m), build(rc, m + 1, t);
}
void pushdown(int p, int s, int t)
{
    if (hold[p])
    {
        val[lc] = val[rc] = val[p];
        hold[lc] = hold[rc] = 1;
        hold[p] = 0;
    }
}
void update(int l, int r, int c, int p, int s, int t)
{
    if (l <= s && t <= r)
    {
        val[p] = c, hold[p] = 1;
        return;
    }
    pushdown(p, s, t);
    int m = s + t >> 1;
    if (l <= m)
        update(l, r, c, lc, s, m);
    if (r > m)
        update(l, r, c, rc, m + 1, t);
}
int query(int l, int r, int p, int s, int t)
{
    if (l <= s && t <= r)
        return val[p];
    pushdown(p, s, t);
    int m = s + t >> 1;
    return l <= m ? query(l, r, lc, s, m) : query(l, r, rc, m + 1, t);
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        cout << "Case #" << _ << ":" << endl;
        memset(isRoot, 1, sizeof isRoot);
        memset(h, -1, sizeof h);
        idx = timestamp = 0;
        cin >> n;
        for (int i = 1; i < n; ++i)
        {
            cin >> x >> y;
            add(y, x);
            isRoot[x] = 0;
        }
        int root = 1;
        for (; !isRoot[root]; ++root)
            ;
        dfs(root);
        build(1, dfn[root], dfr[root]);
        cin >> m;
        while (m-- && cin >> op >> x)
            if (op[0] == 'T')
                cin >> y, update(dfn[x], dfr[x], y, 1, dfn[root], dfr[root]);
            else
                cout << query(dfn[x], dfr[x], 1, dfn[root], dfr[root]) << endl;
    }
    return 0;
}

HDU-4578 Transformation

1
// TODO

HDU-4614 Vases and Flowers

HDU-4553 约会安排

POJ-1177 Picture

HDU-1255 覆盖的面积

HDU-1542 Atlantis

HDU-3642 Get The Treasury