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

相关文章

MySQL中的交叉连接、自然连接和内连接查询详解

《MySQL中的交叉连接、自然连接和内连接查询详解》:本文主要介绍MySQL中的交叉连接、自然连接和内连接查询,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、引入二、交php叉连接(cross join)三、自然连接(naturalandroid join)四

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

Docker镜像修改hosts及dockerfile修改hosts文件的实现方式

《Docker镜像修改hosts及dockerfile修改hosts文件的实现方式》:本文主要介绍Docker镜像修改hosts及dockerfile修改hosts文件的实现方式,具有很好的参考价... 目录docker镜像修改hosts及dockerfile修改hosts文件准备 dockerfile 文

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.