HDU 1540 Tunnel Warfare(Segment Tree)

Description

N个点(1 ~ N)，M个操作

D x 破坏点x

Q x 查询与x直接或间接相连的点（包括x自身）

R x 修复最近一次被破坏的点

Analyze

可以用 线段树 || 树状数组 || set

线段树：

a[num].lmax：包含区间左端点的最大连续子区间长度

a[num].rmax：包含区间右端点的最大连续子区间长度

a[num].ans：本区间最大连续子区间长度（仅用于剪枝：==0 return）

举例：

query(int num, int t)
int mid = (a[num].L + a[num].R) >> 1;
if(t <= mid)
{
    if(a[num << 1].rmax >= mid - t + 1)
    {
        ans += a[num << 1].rmax + a[num << 1 | 1].lmax;
        return ;
    }
    else
        query(num << 1, t);
}
else
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;

char s[10];
int n, m, des[N], last, ans;

struct node
{
    int L, R, ans, lmax, rmax;
}a[N << 2 | 1];

void up(int num)
{
    int mid = (a[num].L + a[num].R) >> 1;
    a[num].lmax = a[num << 1].lmax + (a[num << 1].lmax == mid - a[num].L + 1 ? a[num << 1 | 1].lmax : 0);
    a[num].rmax = a[num << 1 | 1].rmax + (a[num << 1 | 1].rmax == a[num].R - mid ? a[num << 1].rmax : 0);
    a[num].ans = max(max(a[num << 1].ans, a[num << 1 | 1].ans), a[num << 1].rmax + a[num << 1 | 1].lmax);
}

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].ans = a[num].lmax = a[num].rmax = 1;

    if(l == r)
        return ;

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);
    up(num);
}

void update(int num, int t, int val)
{
    if(a[num].L > t || a[num].R < t)
        return ;
    if(a[num].L == a[num].R && a[num].L == t)
    {
        a[num].ans = a[num].lmax = a[num].rmax = val;
        return ;
    }

    update(num << 1, t, val);
    update(num << 1 | 1, t, val);
    up(num);
}

void query(int num, int t)
{
    if(a[num].ans == 0 || a[num].L == a[num].R)
    {
        ans += a[num].ans;
        return ;
    }
    int mid = (a[num].L + a[num].R) >> 1;
    if(t <= mid)
    {
        if(a[num << 1].rmax >= mid - t + 1)
        {
            ans += a[num << 1].rmax + a[num << 1 | 1].lmax;
            return ;
        }
        else
            query(num << 1, t);
    }
    else
    {
        if(a[num << 1 | 1].lmax >= t - mid)
        {
            ans += a[num << 1].rmax + a[num << 1 | 1].lmax;
            return ;
        }
        else
            query(num << 1 | 1, t);
    }
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        init(1, 1, n);
        while(m--)
        {
            int t;
            scanf("%s", s);
            if(s[0] == 'D')
            {
                scanf("%d", &t);
                des[++last] = t;
                update(1, t, 0);
            }
            else if(s[0] == 'R')
                update(1, des[last--], 1);
            else
            {
                scanf("%d", &t);
                ans = 0, query(1, t);
                cout << ans << '\n';
            }
        }
    }
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110