E - Tunnel Warfare HDU - 1540 F - Hotel G - 约会安排 HDU - 4553 区间合并

时间：2023-03-08 17:36:55

E - Tunnel Warfare HDU - 1540

对这个题目的思考：首先我们已经意识到这个是一个线段树，要利用线段树来解决问题，但是怎么解决呢，这个摧毁和重建的操作都很简单，但是这个查询怎么查呢，

这个是不是要判断这一个点左边和右边最远的距离，然后相加起来就可以了，所以就是维护一个区间最左边和最右边的值，然后把他们合并就是最大值。

这个最左边的值 pre_max = 子左节点的 pre_max

如果这个 pre_max==len 那就可以合并子右节点的 pre_max

最右值同理

这个都知道了就只剩下细心一点写这个题目了。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <string>

#include <stack>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

typedef long long ll;

struct node

{

    int l, r, len;

    int pre_max, last_max;

}tree[maxn*];

void push_up(int id)

{

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

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

    if (tree[id << ].len == tree[id << ].pre_max) tree[id].pre_max += tree[id<<|].pre_max;

    if (tree[id <<  | ].len == tree[id <<  | ].last_max) tree[id].last_max += tree[id << ].last_max;

    // printf("tree[%d].max=%d tree[%d].min=%d\n", id, tree[id].pre_max, id, tree[id].last_max);

    // printf("tree[%d].max=%d tree[%d].min=%d\n", id << 1, tree[id << 1].pre_max, id << 1, tree[id << 1].last_max);

    // printf("tree[%d].max=%d tree[%d].min=%d\n", id << 1 | 1, tree[id << 1 | 1].pre_max, id << 1 | 1, tree[id << 1 | 1].last_max);

}

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].last_max = tree[id].pre_max = ;

        return;

    }

    int mid = (l + r) >> ;

    build(id << , l, mid);

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

    push_up(id);

}

void update(int id,int pos,int val)

{

    //printf("id=%d pos=%d val=%d\n", id, pos, val);

    int l = tree[id].l;

    int r = tree[id].r;

    if(l==r)

    {

        tree[id].last_max = tree[id].pre_max = val;

        return;

    }

    int mid = (l + r) >> ;

    if (pos <= mid) update(id << , pos, val);

    else update(id <<  | , pos, val);

    push_up(id);

}

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

{

    int l = tree[id].l;

    int r = tree[id].r;

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

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

    int mid = (l + r) >> ;

    int ans = , res = ;

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

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

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

    if (ans >= mid - x + ) return ans += res;//这个区间长度就是mid-x+1 因为mid 是在里面的所以要+1

    return ans;

}

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

    int l = tree[id].l;

    int r = tree[id].r;

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

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

    int mid = (l + r) >> ;

    int ans = , res = ;

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

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

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

    if (res >= y - mid) res += ans;//区间长度为 y-mid mid不在里面

    return res;

}

int main()

{

    int m, n;

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

    {

        stack<int>sta;

        build(, , n);

        while(m--)

        {

            char s[];

            int x;

            scanf("%s", s);

            if(s[]=='D')

            {

                scanf("%d", &x);

                sta.push(x);

                update(, x, );

            }

            else if(s[]=='R')

            {

                if(!sta.empty())

                {

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

                    update(, num, );

                }

            }

            else if(s[]=='Q')

            {

                scanf("%d", &x);

                int ans = query_pre(, x, n);

                ans += query_last(, , x);

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

                else printf("0\n");

            }

        }

    }

    return ;

}

线段树的区间合并

对这个题目的思考：这个题目不太会写，对于区间合的基本套路还是不太熟悉，这个题目看了题解之后(推荐题解 题解传送门）还是很清楚的。
我们知道这个是一个区间合并的线段树，和区间息息相关，这个要求长度为 w 的最左边的区间，还要求起点。
长度确定，所以我们就一个域是求最大长度的，因为要最左边的区间，而且我们要求最大长度就有合并操作，
所以我们要确定一个从左边开始最长的和从右边开始最长的，这个就和上面的差不多。
这个就是大致思路，剩下就是一些细节了。
一定要仔细点写，然后wa到哭
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <string>

#include <stack>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

typedef long long ll;

struct node {

    int l, r, lazy, len;

    int pre_max, last_max, max;

}tree[maxn * ];

void push_up(int id) {

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

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

    if (tree[id << ].pre_max == tree[id << ].len) tree[id].pre_max += tree[id <<  | ].pre_max;

    if (tree[id <<  | ].last_max == tree[id <<  | ].len) tree[id].last_max += tree[id << ].last_max;

    tree[id].max = max(max(tree[id<<].max, tree[id<<|].max), tree[id << ].last_max + tree[id <<  | ].pre_max);

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

}

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

    tree[id].l = l;

    tree[id].r = r;

    tree[id].lazy = -;

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

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

    if (l == r) return;

    int mid = (l + r) >> ;

    build(id << , l, mid);

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

}

void push_down(int id) {

    if (tree[id].lazy != -) {

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

        if (tree[id].lazy) {

            tree[id << ].last_max = tree[id << ].pre_max = tree[id << ].max = tree[id << ].len;

            tree[id <<  | ].last_max = tree[id <<  | ].pre_max = tree[id <<  | ].max = tree[id <<  | ].len;

        }

        else {

            tree[id << ].last_max = tree[id << ].pre_max = tree[id << ].max = ;

            tree[id <<  | ].last_max = tree[id <<  | ].pre_max = tree[id <<  | ].max = ;

        }

        tree[id].lazy = -;

    }

}

void update(int id, int x, int y, int val) {

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

    int l = tree[id].l;

    int r = tree[id].r;

    if (x == l && y == r) {

        tree[id].lazy = val;

        if (val) tree[id].last_max = tree[id].pre_max = tree[id].max = tree[id].len;

        else tree[id].last_max = tree[id].pre_max = tree[id].max = ;

        return;

    }

    push_down(id);

    int mid = (l + r) >> ;

    if (y <= mid) update(id << , x, y, val);

    else if (mid +  <= x) update(id <<  | , x, y, val);

    else {

        update(id << , x, mid, val);

        update(id <<  | , mid + , y, val);

    }

    push_up(id);

}

int query(int id, int val) {

    int l = tree[id].l;

    int r = tree[id].r;

    //printf("id=%d l=%d r=%d\n", id, l, r);

    if (l == r) return l;

    int mid = (l + r) >> ;

    push_down(id);

    if (tree[id << ].max >= val) return query(id << , val);

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

    if (tree[id << ].last_max + tree[id <<  | ].pre_max >= val) return mid - tree[id << ].last_max + ;

    //printf("tree[%d].last=%d tree[%d].pre=%d id2=%d\n", id<<1,tree[id<<1].last_max,id<<1|1,tree[id<<1|1].pre_max,id);

    return query(id <<  | , val);

}

int main() {

    int n, m;

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

        build(, , n);

        while (m--) {

            int opt, x, y;

            scanf("%d", &opt);

            if (opt == ) {

                scanf("%d", &x);

                if (tree[].max < x) {

                    printf("0\n");

                    continue;

                }

                int ans = query(, x);

                if (ans) update(, ans, ans + x - , );

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

            }

            else {

                scanf("%d%d", &x, &y);

                update(, x, x + y - , );

            }

        }

    }

    return ;

}

线段树

G - 约会安排

这个题目 ：

如果是 DS 就是普通的查找，如果找到就输出最靠前的时间点，这个和上面的操作很像，然后更新。

如果是 NS 就要进行两次查找，第一次是普通查找，没有找到就是二级查找，这个二级查找就是一种覆盖，然后更新。

如果是 study 那就是清空为0 的操作。

这个就是相当于建了两棵树，一颗女神树，一颗基友树，处理女神树的时候要更新基友树，但是处理基友树就不需要更新女神树。

这个题目一定要注意 输出答案

描述中的“如果找到，就说“X,let’s fly”（此处，X为开始时间）…"
和Output中的 “X,let's fly”
里的“ ’ ”和 “ ' ” 不是一个符号，别复制错了！！！

#include <cstdio>//描述中的“如果找到，就说“X,let’s fly”（此处，X为开始时间）…"

#include <cstdlib>//和Output中的 “X, let's fly”

#include <cstring>//里的“ ’ ”和 “ ' ” 不是一个符号，别复制错了！！！

#include <queue>

#include <vector>

#include <algorithm>

#include <string>

#include <stack>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

typedef long long ll;

struct node {

    int len;

    int lsum, rsum, sum;//1 级的

    int lmax, rmax, max;//2 级的

}tree[maxn * ];

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

    tree[id].max = tree[id].lmax = tree[id].rmax = r - l + ;

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

    if (l == r) return;

    int mid = (l + r) >> ;

    build(id << , l, mid);

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

}

void push_up(int id) {

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

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

    if (tree[id << ].lsum == tree[id << ].len) tree[id].lsum += tree[id <<  | ].lsum;

    if (tree[id <<  | ].rsum == tree[id <<  | ].len) tree[id].rsum += tree[id << ].rsum;

    tree[id].sum = max(max(tree[id << ].sum, tree[id <<  | ].sum), tree[id << ].rsum + tree[id <<  | ].lsum);

    tree[id].sum = max(tree[id].sum, tree[id].lsum);

    tree[id].sum = max(tree[id].sum, tree[id].rsum);

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

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

    if (tree[id << ].lmax == tree[id << ].len) tree[id].lmax += tree[id <<  | ].lmax;

    if (tree[id <<  | ].rmax == tree[id <<  | ].len) tree[id].rmax += tree[id << ].rmax;

    tree[id].max = max(max(tree[id << ].max, tree[id <<  | ].max), tree[id << ].rmax + tree[id <<  | ].lmax);

    tree[id].max = max(tree[id].max, tree[id].lmax);

    tree[id].max = max(tree[id].max, tree[id].rmax);

}

void push_down(int id) {

    if(tree[id].max==tree[id].len)

    {

        tree[id << ].max = tree[id << ].lmax = tree[id << ].rmax = tree[id << ].len;

        tree[id <<  | ].max = tree[id <<  | ].lmax = tree[id <<  | ].rmax = tree[id <<  | ].len;

    }

    if(tree[id].max==)

    {

        tree[id << ].max = tree[id << ].lmax = tree[id << ].rmax = ;

        tree[id <<  | ].max = tree[id <<  | ].lmax = tree[id <<  | ].rmax = ;

    }

    if(tree[id].sum==tree[id].len)

    {

        tree[id << ].sum = tree[id << ].lsum = tree[id << ].rsum = tree[id << ].len;

        tree[id <<  | ].sum = tree[id <<  | ].lsum = tree[id <<  | ].rsum = tree[id <<  | ].len;

    }

    if(tree[id].sum==)

    {

        tree[id << ].sum = tree[id << ].lsum = tree[id << ].rsum = ;

        tree[id <<  | ].sum = tree[id <<  | ].lsum = tree[id <<  | ].rsum = ;

    }

}

void update(int id, int l, int r, int x, int y, int val) {

    if (x <= l && y >= r) {

        if (val == ) {

            tree[id].max = tree[id].lmax = tree[id].rmax = ;

            tree[id].sum = tree[id].lsum = tree[id].rsum = ;

        }

        if (val == ) {

            tree[id].sum = tree[id].lsum = tree[id].rsum = ;

        }

        if (val == ) {

            tree[id].max = tree[id].lmax = tree[id].rmax = tree[id].len;

            tree[id].sum = tree[id].lsum = tree[id].rsum = tree[id].len;

        }

        return;

    }

    push_down(id);

    int mid = (l + r) >> ;

    if (x <= mid) update(id << , l, mid, x, y, val);

    if (y > mid) update(id <<  | , mid + , r, x, y, val);

    push_up(id);

}

int query_1(int id, int l, int r, int val) {

    if (l == r) return l;

    int mid = (l + r) >> ;

    push_down(id);

    if (tree[id << ].sum >= val) return query_1(id << , l, mid, val);

    if (tree[id << ].rsum + tree[id <<  | ].lsum >= val) return mid - tree[id << ].rsum + ;

    return query_1(id <<  | , mid + , r, val);

}

int query_2(int id,int l,int r,int val)

{

    if (l == r) return l;

    int mid = (l + r) >> ;

    push_down(id);

    if (tree[id << ].max >= val) return query_2(id << , l, mid, val);

    if (tree[id << ].rmax + tree[id <<  | ].lmax >= val) return mid - tree[id << ].rmax + ;

    return query_2(id <<  | , mid + , r, val);

}

int main()

{

    int t;

    scanf("%d", &t);

    for(int cas=;cas<=t;cas++)

    {

        int n, m, x, y;

        scanf("%d%d", &n, &m);

        build(, , n);

        printf("Case %d:\n", cas);

        while(m--)

        {

            char s[];

            scanf("%s", s);

            if(s[]=='D')

            {

                scanf("%d", &x);

                if(tree[].sum<x)

                {

                    printf("fly with yourself\n");

                    continue;

                }

                int ans = query_1(, , n, x);

                printf("%d,let's fly\n", ans);

                update(, , n, ans, x + ans - , );

            }

            if(s[]=='N')

            {

                scanf("%d", &x);

                if(tree[].sum>=x)

                {

                    int ans = query_1(, , n, x);

                    printf("%d,don't put my gezi\n", ans);

                    update(, , n, ans, x + ans - , );

                    continue;

                }

                if(tree[].max<x)

                {

                    printf("wait for me\n");

                    continue;

                }

                int ans = query_2(,,n,x);

                printf("%d,don't put my gezi\n", ans);

                update(, , n, ans, x + ans - , );

            }

            if(s[]=='S')

            {

                scanf("%d%d", &x, &y);

                update(, , n, x, y, );

                printf("I am the hope of chinese chengxuyuan!!\n");

            }

        }

    }

}

线段树