HDU 4031 Attack(树状数组修改区间查询点)

2024-06-01 21:18

本文主要是介绍HDU 4031 Attack(树状数组修改区间查询点),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem Description
Today is the 10th Annual of “September 11 attacks”, the Al Qaeda is about to attack American again. However, American is protected by a high wall this time, which can be treating as a segment with length N. Al Qaeda has a super weapon, every second it can attack a continuous range of the wall. American deployed N energy shield. Each one defends one unit length of the wall. However, after the shield defends one attack, it needs t seconds to cool down. If the shield defends an attack at kth second, it can’t defend any attack between (k+1)th second and (k+t-1)th second, inclusive. The shield will defend automatically when it is under attack if it is ready.

During the war, it is very important to understand the situation of both self and the enemy. So the commanders of American want to know how much time some part of the wall is successfully attacked. Successfully attacked means that the attack is not defended by the shield.

Input
The beginning of the data is an integer T (T ≤ 20), the number of test case.
The first line of each test case is three integers, N, Q, t, the length of the wall, the number of attacks and queries, and the time each shield needs to cool down.
The next Q lines each describe one attack or one query. It may be one of the following formats
1. Attack si ti
  Al Qaeda attack the wall from si to ti, inclusive. 1 ≤ si ≤ ti ≤ N
2. Query p
  How many times the pth unit have been successfully attacked. 1 ≤ p ≤ N
The kth attack happened at the kth second. Queries don’t take time.
1 ≤ N, Q ≤ 20000
1 ≤ t ≤ 50

Output
For the ith case, output one line “Case i: ” at first. Then for each query, output one line containing one integer, the number of time the pth unit was successfully attacked when asked.

Sample Input
  
2 3 7 2 Attack 1 2 Query 2 Attack 2 3 Query 2 Attack 1 3 Query 1 Query 3 9 7 3 Attack 5 5 Attack 4 6 Attack 3 7 Attack 2 8 Attack 1 9 Query 5 Query 3

Sample Output
  
Case 1: 0 1 0 1 Case 2: 3 2

题意:

长度为n的城墙,进行q次询问,护盾冷却时间为cd,每次询问包含Attack和Query,Attack的时候是过一秒城墙l,r段被攻击,Query是询问输出城墙某一点到这个时间被攻击到的次数。

思路:

树状数组,通常树状数组是更新点询问区间,而这题是要更新区间询问点,对于更新区间,其实可以转化为更新点:对于区间[l,r],我们更新点l为正,

点r+1为负,这样一来等效于更新了区间。然后在询问点的时候,对于我们这个保存方式,保存的是城墙被攻击的次数,所以要转化一下,

被攻击到的次数=总攻击次数-成功保护的次数。每次询问到一个点的时候,记录下从开始到当前时间这个点一共成功保护了多少次。

代码:

#include <stdio.h>
#include <string.h>const int N = 20005;int t, n, q, cd, bit[N], pro[N], time, pt[N], rt[N], lt[N];void Add(int x, int v) {while (x <= n) {bit[x] += v;x += (x&(-x));}
}int Sum(int x) {int ans = 0;while (x > 0) {ans += bit[x];x -= (x&(-x));}return ans;
}void init() {time = 0;memset(bit, 0, sizeof(bit));memset(pro, 0, sizeof(pro));memset(lt, 0, sizeof(lt));memset(rt, 0, sizeof(rt));memset(pt, 0, sizeof(pt));scanf("%d%d%d", &n, &q, &cd);
}void solve() {char Q[10];for (int i = 0; i < q; i++) {scanf("%s", Q);if (Q[0] == 'A') {int l, r;scanf("%d%d", &l, &r);Add(l, 1);Add(r + 1, -1);lt[time] = l;rt[time] = r;time++;}else {int num; scanf("%d", &num);for (int j = pt[num]; j < time; j++) {if (num >= lt[j] && num <= rt[j]) {pt[num] = j + cd;pro[num]++;j += cd - 1;}}printf("%d\n", Sum(num) - pro[num]);}}
}int main() {int cas = 0;scanf("%d", &t);while (t--) {printf("Case %d:\n", ++cas);init();solve();}return 0;
}


这篇关于HDU 4031 Attack(树状数组修改区间查询点)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1022138

相关文章

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Linux修改pip临时目录方法的详解

《Linux修改pip临时目录方法的详解》在Linux系统中,pip在安装Python包时会使用临时目录(TMPDIR),但默认的临时目录可能会受到存储空间不足或权限问题的影响,所以本文将详细介绍如何... 目录引言一、为什么要修改 pip 的临时目录?1. 解决存储空间不足的问题2. 解决权限问题3. 提

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Linux文件名修改方法大全

《Linux文件名修改方法大全》在Linux系统中,文件名修改是一个常见且重要的操作,文件名修改可以更好地管理文件和文件夹,使其更具可读性和有序性,本文将介绍三种在Linux系统下常用的文件名修改方法... 目录一、引言二、使用mv命令修改文件名三、使用rename命令修改文件名四、mv命令和rename命

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名,员

Linux下修改hostname的三种实现方式

《Linux下修改hostname的三种实现方式》:本文主要介绍Linux下修改hostname的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下修改ho编程stname三种方式方法1:修改配置文件方法2:hFvEWEostnamectl命