【线段树左右衔接区间更新查找问题】I - Tunnel Warfare HDU - 1540

我会带着你远行 2022-06-10 10:16 175阅读 0赞

Think:  
1知识点：线段树左右衔接区间更新查找问题  
2题意：数，线段，三种操作，D操作(删除一个数)，R操作(回复前一个删除的数)，Q操作(查询一个数所在线段的最大连续线段长度)

[vjudge题目链接][vjudge]

[建议参考博客][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    
    using namespace std;
    
    #define MID int mid = (tree[rt].l+tree[rt].r)>>1
    #define lson rt<<1
    #define rson rt<<1|1
    
    const int N = 51400;
    
    struct Tree{
        int l, r;
        int lsum, rsum, msum;/*lsum表示从区间左端点开始的最大连续值；rsum代表从区间右端点开始的最大值；msum表示整个区间的最大连续值*/
        int len(){
            return (r-l+1);
        }
    }tree[N<<2];
    
    void Build(int l, int r, int rt);
    void Pushup(int rt);
    void up_v(int p, int v, int rt);
    int Query(int p, int rt);
    
    int main(){
        int n, m, i, p;
        char st[14];
        while(~scanf("%d %d", &n, &m)){
            Build(1, n, 1);
            stack <int> sta;
            while(!sta.empty()){
                sta.pop();
            }
            for(i = 0; i < m; i++){
                scanf("%s", st);
                if(st[0] == 'D'){
                    scanf("%d", &p);
                    up_v(p, 0, 1);
                    sta.push(p);
                }
                else if(st[0] == 'R'){
                    if(sta.empty())
                        continue;
                    int to = sta.top();
                    sta.pop();
                    up_v(to, 1, 1);
                }
                else if(st[0] == 'Q'){
                    scanf("%d", &p);
                    printf("%d\n", Query(p, 1));
                }
            }
        }
        return 0;
    }
    void Build(int l, int r, int rt){
        tree[rt].l = l, tree[rt].r = r;
        tree[rt].lsum = tree[rt].rsum = tree[rt].msum = tree[rt].len();
        if(l == r)
            return;
        MID;
        Build(l, mid, lson);
        Build(mid+1, r, rson);
    }
    void up_v(int p, int v, int rt){
        if(tree[rt].l == tree[rt].r){
            tree[rt].lsum = tree[rt].rsum = tree[rt].msum = v;
            return;
        }
        MID;
        if(p <= mid)
            up_v(p, v, lson);
        if(p > mid)
            up_v(p, v, rson);
        Pushup(rt);
    }
    void Pushup(int rt){
        tree[rt].lsum = tree[lson].lsum;
        tree[rt].rsum = tree[rson].rsum;
        tree[rt].msum = max(max(tree[lson].msum, tree[rson].msum), tree[lson].rsum+tree[rson].lsum);
        if(tree[lson].lsum == tree[lson].len())/*判断左二子的左连续区间是否为整个区间*/
            tree[rt].lsum += tree[rson].lsum;/*若左二子的左连续区间为整个区间则即可与有右儿子的左连续区间衔接*/
        if(tree[rson].rsum == tree[rson].len())/*判断右儿子的右连续区间是否为整个区间*/
            tree[rt].rsum += tree[lson].rsum;/*若右儿子的右连续区间为整个区间则则即可与左二子的右连续区间衔接*/
    }
    int Query(int p, int rt){
        if(tree[rt].l == tree[rt].r || tree[rt].msum == 0 || tree[rt].msum == tree[rt].len())
            return tree[rt].msum;
        MID;
        if(p <= mid){
            if(p >= tree[lson].r-tree[lson].rsum+1)/*判断p的位置是否在左二子的右连续区间*/
                return Query(p, lson) + Query(mid+1, rson);/*若p在左二子的右连续区间则需要返回p在左二子的连续长度和mid+1在右儿子的连续长度之和,两者衔接*/
            else
                return Query(p, lson);/*若p不在左二子的右连续区间则进行到左子树寻找解*/
        }
        else {
            if(p <= tree[rson].l+tree[rson].lsum-1)/*判断p的位置是否在右儿子的左连续区间*/
                return Query(p, rson) + Query(mid, lson);/*若p在右儿子的左连续区间则需要返回p在右儿子的连续长度和mid在左二子的连续长度之和，两者衔接*/
            else
                return Query(p, rson);/*若p不在右儿子的左连续区间则进行到右子树寻找解*/
        }
    }

[vjudge]: https://vjudge.net/contest/163011#problem/I
[Link 1]: http://blog.csdn.net/just_sort/article/details/51953395