[原创]华中农业大学第五届程序设计大赛 I Candies [线段树]【数据结构】

2017-05-26 22:03:13 Tabris_ 阅读数：309

博客爬取于2020-06-14 22:40:30
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72773996

题目链接:http://acm.hzau.edu.cn/problem.php?id=1207
——————————————————————————————————————
1207: Candies
Time Limit: 2 Sec Memory Limit: 1280 MB
Submit: 249 Solved: 39
[Submit][Status][Web Board]
Description
Xiao Ming likes those N candies he collects very much. There are two kinds of candies, A and B. One day, Xiao Ming puts his candies in a row and plays games. And he can replace the Lth candy to the Rth candy with the same kind of candies. Now, he wonder that if he eats the Lth candy to Rth candy, he can eat how many B candy continuously at most. For each Xiao Ming’s query, give the number of the B candy he can eat continuously at most.

Input
In the first line, there is an integer T, indicates the number of test cases.

For each case, there are two integers N and M in the first line, indicate the number of candies and the time of Xiao Ming’s operations.

The second line is a N-length string consist of character A and B, indicates the row of candies Xiao Ming put.

The next M line is Xiao Ming’s operations. There are two kind of operations:

  1. 1 L R v, indicate Xiao Ming replaces the Lth candy to the Rth candy with A candies (v==1) or B candies ( v == 2 ).

  2. 2 L R, indicate Xiao Ming wonder that there are how many continuous B candies between the Lth candy to the Rth candy most.

Output
In each case, the first line is “Case #k: “, k indicates the case number.

For each query, output the number of the most continuous B candies.

Sample Input
1
5 3
ABABB
2 1 3
1 2 3 2
2 1 3
Sample Output
Case #1:
1
2

————————————————————————————————————————————
题目大意：
给你一个序列，分别代表AB两种果实，

有两种操作，
1 将区间l，r 全变为（A或B）中操作
2 问你区间l，r 中连续的B最长是多长

解题思路：
线段树维护就好了

因为要有维护两个区间并的情况，所以要维护
sum 当前区间内连续的B的长度
ls 当前左边界开始向右连续B的长度
rs 当前右边界开始向左连续B的长度
lazy 懒标记

然后注意下维护的细节就好

Ps： 本来自己写了份代码，但是写到最后query的时候发现，合并时需要的信息得需要一个结构体来存诸，然而我写的时数组的。。。。。心态爆炸。。 最后厚颜无耻的贴了代码。。。

附本题代码
————————————————————————————————

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
# include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 7;
struct node{
    int l, r, lazy, len;
    int lb, mb, rb;
    void Set_B(int key){ // 对区间内的 lb, mb, rb 进行更改
        if(key == 1) lb = mb = rb = 0;
        else lb = mb = rb = len;
    }
} tree[maxn<<2];
char z[maxn];

int Find_max(int s1, int s2, int s3){
    if(s2 > s1) s1 = s2;
    if(s3 > s1) s1 = s3;
    return s1;
}

void Push_up(int key){ // 向上更新, 区间合并
    int lson = key<<1, rson = key<<1|1;
    tree[key].lb = tree[lson].lb;
    tree[key].rb = tree[rson].rb;
    if(tree[lson].lb == tree[lson].len) tree[key].lb += tree[rson].lb;
    if(tree[rson].rb == tree[rson].len) tree[key].rb += tree[lson].rb;
    tree[key].mb = max(tree[lson].rb + tree[rson].lb, max(tree[lson].mb, tree[rson].mb));
}

void Push_down(int key){ // 向下更新
    if(tree[key].lazy != 0){
        int lson = key<<1, rson = key<<1|1;
        tree[lson].lazy = tree[rson].lazy = tree[key].lazy;
        tree[lson].Set_B(tree[key].lazy);
        tree[rson].Set_B(tree[key].lazy);
        tree[key].lazy = 0;
    }
}

void Buildtree(int l, int r, int key){ // 建树
    tree[key].l = l;
    tree[key].r = r;
    tree[key].len = r - l + 1;
    tree[key].lazy = 0;
    if(l == r){
        if(z[l] == 'A') tree[key].Set_B(1);
        else tree[key].Set_B(2);
        return;
    }
    int mid = (l + r) >> 1;
    Buildtree(l, mid, key<<1);
    Buildtree(mid+1, r, key<<1|1);
    Push_up(key);
}

void Update(int l, int r, int key, int w){ // 更新
    if(l <= tree[key].l && tree[key].r <= r){
        tree[key].lazy = w;
        tree[key].Set_B(w);
        return;
    }
    Push_down(key);
    int mid = (tree[key].l + tree[key].r) >> 1;
    if(l <= mid) Update(l, r, key<<1, w);
    if(mid < r) Update(l, r, key<<1|1, w);
    Push_up(key);
}

node Merge(node p, node q){ // 区间合并, 与向上更新相同
    node tmp;
    tmp.len = p.len + q.len;
    tmp.lb = p.lb;
    tmp.rb = q.rb;
    if(p.lb == p.len) tmp.lb += q.lb;
    if(q.rb == q.len) tmp.rb += p.rb;
    tmp.mb = max(p.rb + q.lb, max(p.mb, q.mb));
    return tmp;
}

node Query(int l, int r, int key){ // 询问
    if(l <= tree[key].l && tree[key].r <= r) return tree[key];
    Push_down(key);
    int mid = (tree[key].l + tree[key].r) >> 1;
    if(r <= mid) return Query(l, r, key<<1);
    else if(mid < l) return Query(l, r, key<<1|1);
    else return Merge(Query(l, mid, key<<1), Query(mid+1, r, key<<1|1));
}

int main(){
    int t, n, q, op, u, v, w;
    int num = 0;
    scanf("%d", &t);
    while(t --){
        scanf("%d %d", &n, &q);
        scanf("%s", z+1);
        Buildtree(1, n, 1);
        printf("Case #%d:\n", ++ num); // 这里很坑，如果后面没有空格会WA掉
        while(q --){
            scanf("%d %d %d", &op, &u, &v);
            if(op == 1){
                scanf("%d", &w);
                Update(u, v, 1, w);
            }
            else{
                node gg = Query(u, v, 1);
                printf("%d\n", Find_max(gg.lb, gg.mb, gg.rb));
            }
        }
    }
    return 0;
}