当前位置: 开发笔记 > 编程语言 > 正文

HDU1540TunnelWarfare（线段树区间合并）

作者：liuc | 来源：互联网 | 2023-09-18 14:40

题意:1-2-3--n连成一条链,三种操作D:毁掉xR:恢复上次毁掉的Q:查询与x直接相连或者间接相邻的数量(包括自己)分析:线段树求区间连续最大和,经

题意: 1-2-3-...-n连成一条链, 三种操作

D: 毁掉x R: 恢复上次毁掉的 Q:查询与x直接相连或者间接相邻的数量(包括自己)

分析: 线段树求区间连续最大和, 经典题目维护区间从左端点开始最大连续和lsum, 同理rsum

查询的时候查看当前是否在子区间的rsum和lsum 范围内是的话答案就是它找不到就是0

用栈来维护被摧毁的城市

代码:

//
//  Created by TaoSama on 2015-09-17
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define pr(x) cout <<#x <<" = " <#define prln(x) cout <<#x <<" = " <const int N = 5e4 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, q;
int lsum[N <<2], rsum[N <<2], stk[N], top;

#define root 1, n, 1
#define lson l, m, rt <<1
#define rson m + 1, r, rt <<1 | 1

void push_up(int rt, int m) {
    lsum[rt] = lsum[rt <<1];
    rsum[rt] = rsum[rt <<1 | 1];
    if(lsum[rt <<1] == m - (m >> 1)) lsum[rt] += lsum[rt <<1 | 1];
    if(rsum[rt <<1 | 1] == m >> 1) rsum[rt] += rsum[rt <<1];
}

void build(int l, int r, int rt) {
    lsum[rt] = rsum[rt] = r - l + 1;
    if(l == r) return;
    int m = l + r >> 1;
    build(lson);
    build(rson);
}

void update(int o, int v, int l, int r, int rt) {
    if(l == r) {
        lsum[rt] = rsum[rt] = v;
        return;
    }
    int m = l + r >> 1;
    if(o <= m) update(o, v, lson);
    else update(o, v, rson);
    push_up(rt, r - l + 1);
}

int query(int o, int l, int r, int rt) {
    if(l == r) return 0;
    int m = l + r >> 1;
    if(o >= m - rsum[rt <<1] + 1 && o <= m + lsum[rt <<1 | 1])
        return rsum[rt <<1] + lsum[rt <<1 | 1];
    if(o <= m) return query(o, lson);
    else return query(o, rson);
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d%d", &n, &q) == 2) {
        build(root);
        top = 0;
        while(q--) {
            char op[2]; int x;
            scanf("%s", op);
            if(*op == 'R') {
                x = stk[--top];
                update(x, 1, root);
            } else {
                scanf("%d", &x);
                if(*op == 'D') {
                    stk[top++] = x;
                    update(x, 0, root);
                } else printf("%d\n", query(x, root));
            }
        }
    }
    return 0;
}

推荐阅读

const
SPOJ2829 TLETime Limit Exceeded 题解及优化方法

本文介绍了SPOJ2829题目的解法及优化方法。题目要求找出满足一定条件的数列，并对结果取模。文章详细解释了解题思路和算法实现，并提出了使用FMT优化的方法。最后，对于第三个限制条件，作者给出了处理方法。文章最后给出了代码实现。 ... [详细]

蜡笔小新 2023-12-09 21:18:30
const
电话号码的字母组合解题思路和代码示例

本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法，可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]

蜡笔小新 2023-12-14 18:50:22
const
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
less
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
const
关于Linq to sql 实现模糊查询 string数组

前景：当UI一个查询条件为多项选择，或录入多个条件的时候，比如查询所有名称里面包含以下动态条件，需要模糊查询里面每一项时比如是这样一个数组条件：newstring[]{兴业银行, ... [详细]

蜡笔小新 2023-12-13 09:34:59
const
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
const
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
const
Which is more efficient: char str[] or char *str?

This article discusses the efficiency of using char str[] and char *str and whether there is any reason to prefer one over the other. It explains the difference between the two and provides an example to illustrate their usage. ... [详细]

蜡笔小新 2023-12-12 10:13:35
数组
数组或散列中的正则表达式排序 - Regex in array or hash - sorting

Ihaveaworkfolderdirectory.我有一个工作文件夹目录。holderDir.glob(*)>holder[ProjectOne, ... [详细]

蜡笔小新 2023-12-10 12:41:53
const
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
const
单击后为什么远程通知操作无效？ - Why remote notification action is doing nothing after clicking?

IhaveconfiguredanactionforaremotenotificationwhenitarrivestomyiOsapp.Iwanttwodiff ... [详细]

蜡笔小新 2023-12-14 15:57:44
const
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:37:34
数组
STL迭代器的种类及其功能介绍

本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系，并详细描述了各个迭代器的功能和使用方法。其中，输入迭代器用于从容器中读取元素，输出迭代器用于向容器中写入元素，正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]

蜡笔小新 2023-12-10 15:17:25
filter
用Vue实现的Demo商品管理效果图及实现代码

本文介绍了一个使用Vue实现的Demo商品管理的效果图及实现代码。 ... [详细]

蜡笔小新 2023-12-10 15:14:25
default
AFNetwork框架（零）使用NSURLSession进行网络请求

本文介绍了AFNetwork框架中使用NSURLSession进行网络请求的方法，包括NSURLSession的配置、请求的创建和执行等步骤。同时还介绍了NSURLSessionDelegate和NSURLSessionConfiguration的相关内容。通过本文可以了解到AFNetwork框架中使用NSURLSession进行网络请求的基本流程和注意事项。 ... [详细]

蜡笔小新 2023-12-10 02:03:27

liuc

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章