HDU 4553 Date arrange(Segment Tree)

Description

中文题目：小明

与DS开黑

与NS约会

学习

Analyze

题目要求：寻找具有某种属性的、连续的最长区间

与HDU 1540相同，都是找符合某一特点的连续的最长区间

那么线段树也是一样的

val：ans、lmax、rmax最长连续空间时间段的长度

此时ans起辅助作用，主角是lmax与rmax，只要down地足够深，要查找的区间总是某些个lmax与rmax的和。

此题维护两棵线段树：DS树与NS树

①DS x:

若DS树有长度足够的区间，去DS树上找结束位置(-x即起始位置)

将DS树对应区间三个val置零

找不到区间直接输出相应字符串

②NS x:

若DS树有长度足够的区间，去DS树上找结束位置(-x即起始位置)

将DS树和NS树对应区间三个val置零

若DS树没有足够空间，但NS树有足够空间，去NS书上找

将DS树和NS树对应区间三个val置零

若都没有足够空间，输出相应字符串

③STUDY x y:

将DS树和NS树对应区间恢复为1（即val值恢复为区间长度）

另外代码中的query函数，三分去找够大的空闲区间的第x时刻

Code

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

char s[10];
int n, m;

///0 for DS and 1 for NS
int lmax[N << 2 | 1][2];
int rmax[N << 2 | 1][2];
int ans[N << 2 | 1][2];


void down(int o, int L, int R)///related to the function of"update"
{
    int mid = (L + R) >> 1;
    for(int idx = 0; idx < 2; ++idx)
    {
        if(ans[o][idx] == R - L + 1)
        {
            lmax[o << 1][idx] = rmax[o << 1][idx] = ans[o << 1][idx] =  mid - L + 1;
            lmax[o << 1 | 1][idx] = rmax[o << 1 | 1][idx] = ans[o << 1 | 1][idx] = R - mid;
        }
        if(ans[o][idx] == 0)
        {
            lmax[o << 1][idx] = rmax[o << 1][idx] = ans[o << 1][idx] =  0;
            lmax[o << 1 | 1][idx] = rmax[o << 1 | 1][idx] = ans[o << 1 | 1][idx] = 0;
        }
    }
}

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

void build(int o, int l, int r)
{
    if(l == r)
    {
        lmax[o][0] = rmax[o][0] = ans[o][0] = lmax[o][1] = rmax[o][1] = ans[o][1] = 1;
        return ;
    }

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

void update(int o, int L, int R, int l, int r, int idx)
{
    if(L > r || R < l)
        return ;
    if(L >= l && R <= r)
    {
        if(idx == 0)///DS or NS1
            lmax[o][0] = rmax[o][0] = ans[o][0] = 0;
        else///NS2 or Study
        {
            lmax[o][0] = rmax[o][0] = ans[o][0] = (idx == 1 ? 0 : R - L + 1);
            lmax[o][1] = rmax[o][1] = ans[o][1] = (idx == 1 ? 0 : R - L + 1);
        }
        return ;
    }
    if(L == R)
        return ;

    down(o, L, R);
    int mid = (L + R) >> 1;
    update(o << 1, L, mid, l, r, idx);
    update(o << 1 | 1, mid + 1, R, l, r, idx);
    up(o, L, R);
}

int query(int o, int L, int R, int x, int idx)
{
    if(L == R)
        return L;

    down(o, L, R);
    int mid = (L + R) >> 1;
    if(ans[o << 1][idx] >= x)
        return query(o << 1, L, mid, x, idx);
    else if(rmax[o << 1][idx] + lmax[o << 1 | 1][idx] >= x)
        return mid - rmax[o << 1][idx] + x;
    else
        return query(o << 1 | 1, mid + 1, R, x, idx);
    up(o, L, R);
}

int main()
{
    int _, cnt = 1;
    scanf("%d", &_);
    while(_--)
    {
        printf("Case %d:\n", cnt++);
        scanf("%d %d", &n, &m);
        build(1, 1, n);

        int x, y;
        while(m--)
        {
            scanf("%s%d", s, &x);
            if(s[0] == 'D')
            {
                if(ans[1][0] >= x)
                {
                    int t = query(1, 1, n, x, 0);
                    t = t - x + 1;
                    printf("%d,let's fly\n", t);
                    update(1, 1, n, t, t + x - 1, 0);
                }
                else
                    cout << "fly with yourself\n";
            }
            else if(s[0] == 'N')
            {
                if(ans[1][0] >= x)
                {
                    int t = query(1, 1, n, x, 0);
                    t = t - x + 1;
                    printf("%d,don't put my gezi\n", t);
                    update(1, 1, n, t, t + x - 1, 1);
                }
                else if(ans[1][1] >= x)
                {
                    int t = query(1, 1, n, x, 1);
                    t = t - x + 1;
                    printf("%d,don't put my gezi\n", t);
                    update(1, 1, n, t, t + x - 1, 1);
                }
                else
                    cout << "wait for me\n";
            }
            else
            {
                scanf("%d", &y);
                update(1, 1, n, x, y, 2);
                cout << "I am the hope of chinese chengxuyuan!!\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
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

Attention

区间更新：该down的时候就应该down
单点更新：本质也是区间更新，只不过这个“区间”已经最低而不可分割了，故不需要down
结论：纯粹单点更新的题目不需要down，其他但凡涉及区间更新的题目都需要down(而且是根据update里面的内容来down)

数组代替结构体实现的线段树不一定可以完全由memset代替初始化，遇到需要up的就免不了

build函数里val的初始化要小心，考虑up的影响，可能与实际情况不一样！

if(A == B)
    D = E;
if(A == C)
    D = F;
1
2
3
4

不可以写成：

D = (A == B ? E : F)
1

因为上面是两个if，并非if-else

Debug半天…