Tunnel Warfare 线段树 区间合并|最大最小值

B - Tunnel WarfareHDU - 1540

这个有两种方法，一个是区间和并，这个我个人感觉异常恶心

第二种方法就是找最大最小值 kuangbin——线段树专题 H - Tunnel Warfare <-- 这个博客讲的很清楚

#include <cstdio>//法一：最大值最小值法，这个就是每一个点，如果这个点没有被摧毁，那就找到这个点最左边的和最右边的

#include <cstdlib>//最大-最小+1.这个就是这个最大连续长度。

#include <queue>//建树，很简单，主要就是query和update。

#include <algorithm>//这个地方的怎么去找一个包含一个数的一个区间的最大最小值呢？

#include <vector>//这个就是从上面往下面查询的过程中，就去找，如果是找最大值就去max，最小值就取min

#include <cstring>//这个要注意建树，这个区间的最大值的意思是，小于等于这个数的最大的被炸了的村庄，这个就说明，开始最大值为0，因为没有任何一个村庄被炸

#include <string>//区间的最小值，意思是大于等于这个数，被炸了的村庄的最小值，开始为n+1.因为没有村庄被炸。

#include <iostream>

#include <stack>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

struct node

{

    int l, r;

    int mx, mn;

}tree[maxn*];

int n;

void build(int id,int l,int r)

{

    tree[id].l = l;

    tree[id].r = r;

    if(l==r)

    {

        tree[id].mn = n+;

        tree[id].mx = ;

        return;

    }

    int mid = (l + r) >> ;

    build(id << , l, mid);

    build(id <<  | , mid + , r);

    tree[id].mx = max(tree[id << ].mx, tree[id <<  | ].mx);

    tree[id].mn = min(tree[id << ].mn, tree[id <<  | ].mn);

}

void update_max(int id,int x,int z)

{

    if(tree[id].l==tree[id].r)

    {

        tree[id].mx = z;

        return;

    }

    int mid = (tree[id].l + tree[id].r) >> ;

    if(x<=mid) update_max(id << , x, z);

    if (x > mid) update_max(id <<  | , x, z);

    tree[id].mx = max(tree[id << ].mx, tree[id <<  | ].mx);

}

void update_min(int id,int x,int z)

{

    if(tree[id].l==tree[id].r)

    {

        tree[id].mn = z;

        return;

    }

    int mid = (tree[id].l + tree[id].r) >> ;

    if (x <= mid) update_min(id << , x, z);

    if (x > mid) update_min(id <<  | , x, z);

    tree[id].mn = min(tree[id << ].mn, tree[id <<  | ].mn);

}

int query_max(int id,int x,int y)

{

    int ans = ;

    if(x<=tree[id].l&&y>=tree[id].r)

    {

        return tree[id].mx;

    }

    int mid = (tree[id].l + tree[id].r) >> ;

    if (x <= mid) ans = max(ans, query_max(id << , x, y));

    if (y > mid) ans = max(ans, query_max(id <<  | , x, y));

    return ans;

}

int query_min(int id,int x,int y)

{

    int ans = inf;

    if(x<=tree[id].l&&y>=tree[id].r)

    {

        return tree[id].mn;

    }

    int mid = (tree[id].l + tree[id].r) >> ;

    if (x <= mid) ans = min(ans, query_min(id << , x, y));

    if (y > mid) ans = min(ans, query_min(id <<  | , x, y));

    return ans;

}

int main()

{

    int m, x;

    while(cin >> n >> m)

    {

        stack<int>sta;

        build(, , n);

        while(m--)

        {

            char s[];

            scanf("%s", s);

            if(s[]=='D')

            {

                cin >> x;

                update_max(, x, x);

                update_min(, x, x);

                sta.push(x);

            }

            if(s[]=='R')

            {

                int y = sta.top(); sta.pop();

                update_max(, y, );

                update_min(, y, n + );

            }

            if(s[]=='Q')

            {

                cin >> x;

                int L = query_min(, x, n + );

                int R = query_max(, , x);

                //printf("%d %d\n", L, R);

                if (L == R) printf("0\n");

                else printf("%d\n", L - R - );

            }

        }

    }

    return ;

}

方法一

//法二：区间合并，这个应该更好懂一点，就是维护一下一个区间的前缀后缀长度

//这个更新应该比较简单，

#include <cstdio>

#include <cstdlib>

#include <queue>

#include <algorithm>

#include <vector>

#include <cstring>

#include <string>

#include <iostream>

#include <stack>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

struct node

{

    int l, r, len;

    int max_pre, max_last;

}tree[maxn*];

void push_up(int id)

{

    tree[id].max_pre = tree[id << ].max_pre;

    tree[id].max_last = tree[id <<  | ].max_last;

    if (tree[id << ].max_pre == tree[id << ].len)

    {

        tree[id].max_pre += tree[id <<  | ].max_pre;

    }

    if(tree[id<<|].max_last==tree[id<<|].len)

    {

        tree[id].max_last += tree[id << ].max_last;

    }

}

void build(int id,int l,int r)

{

    tree[id].l = l;

    tree[id].r = r;

    tree[id].len = r - l + ;

    if(l==r)

    {

        tree[id].max_pre = tree[id].max_last = ;

        return;

    }

    int mid = (l + r) >> ;

    build(id << , l, mid);

    build(id <<  | , mid + , r);

    push_up(id);

}

void update(int id,int x,int z)

{

    if(tree[id].l==tree[id].r)

    {

        tree[id].max_pre = z;

        tree[id].max_last = z;

        return;

    }

    int mid = (tree[id].l + tree[id].r) >> ;

    if (x <= mid) update(id << , x, z);

    else update(id <<  | , x, z);

    push_up(id);

}

int query_pre(int id,int x,int y)

{

    int ans = , res = ;

    if(x<=tree[id].l&&y>=tree[id].r)

    {

        //printf("tree[%d].max_pre=%d\n", id, tree[id].max_pre);

        return tree[id].max_pre;

    }

    //printf("id=%d x=%d y=%d\n", id, x, y);

    int mid = (tree[id].l + tree[id].r) >> ;

    if (x <= mid) ans=query_pre(id << , x, y);

    if (y > mid) res=query_pre(id <<  | , x, y);

    //printf("id=%d ans=%d res=%d mid=%d\n",id, ans, res,mid);

    if (ans >= mid - x + )

    {

        //printf("tree[%d].max_pre=%d mid=%d x=%d\n",id, tree[id].max_pre, mid, x);

        ans += res;

    }

    return ans;

}

int query_last(int id,int x,int y)

{

    int ans = , res = ;

    if (x <= tree[id].l&&y >= tree[id].r)

    {

        //printf("tree[%d].last=%d\n", id, tree[id].max_last);

        return tree[id].max_last;

    }

    //printf("id=%d x=%d y=%d\n", id, x, y);

    int mid = (tree[id].l + tree[id].r) >> ;

    if (x <= mid) ans = query_last(id << , x, y);

    if (y > mid) res = query_last(id <<  | , x, y);

    //printf("id=%d mid=%d ans=%d res=%d\n", id, mid,ans, res);

    if (res >= y-mid)

    {

        //printf("tree[%d].max_last=%d  mid=%d x=%d\n",id,tree[id].max_last, mid, x);

        res += ans;

    }

    return res;

}

int main()

{

    int n, m;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        stack<int>sta;

        build(, , n);

        while(m--)

        {

            char s[];

            scanf("%s", s);

            if(s[]=='D')

            {

                int x;

                cin >> x;

                update(, x, );

                sta.push(x);

            }

            if(s[]=='R')

            {

                int y = sta.top(); sta.pop();

                update(, y, );

            }

            if(s[]=='Q')

            {

                int x;

                cin >> x;

                int ans = query_pre(, x, n);

                ans += query_last(, , x);

                if(ans) printf("%d\n", ans-);

                else printf("0\n");

            }

        }

    }

    return ;

}

/*

7 10

D 3

D 6

D 5

Q 4

Q 5

R

Q 4

R

Q 4

Q 3

 */

方法二