HDU-4031-Attack(树状数组)
数组 HDU 树状 Attack
2023-09-14 09:09:01 时间
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.
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
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
Source
思路:成功攻击的次数=总次数-被防御的次数。
用树状数组维护总次数,一个辅助数组记录当前点被攻击之后恢复的时间,还有一个数组记录当前点的被防御次数。
#include <stdio.h> int n,node[20005],ls[20005],rs[20005],pos[20005],c[20005]; int lowbit(int x) { return x & -x; } int sum(int x) { int res=0; while(x>0) { res+=node[x]; x-=lowbit(x); } return res; } void add(int x,int val) { while(x<=n) { node[x]+=val; x+=lowbit(x); } } int main() { int T,q,t,i,a,b,cnt,cases=1; char s[10]; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&q,&t); cnt=0; for(i=0;i<=n;i++) c[i]=node[i]=pos[i]=0; printf("Case %d:\n",cases++); while(q--) { scanf("%s",s); if(s[0]=='A') { scanf("%d%d",&a,&b); ls[cnt]=a; rs[cnt]=b; cnt++; add(a,1); add(b+1,-1); } else { scanf("%d",&a); for(i=pos[a];i<cnt;i++) { if(a>=ls[i] && a<=rs[i] && i>=pos[a]) { pos[a]=i+t; c[a]++; i+=t-1; } } printf("%d\n",sum(a)-c[a]); } } } }
相关文章
- Java实现 LeetCode 629 K个逆序对数组(动态规划+数学)
- Java实现 LeetCode 189 旋转数组
- jquery遍历数组的方式
- 749. 数组的上方区域
- LeetCode-53. 最大子数组和
- C++:C++编程语言学习之数组/指针的简介、案例应用之详细攻略
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-49 算法训练 寻找数组中最大值
- js 判断数组中的值是否都相等
- 【华为机试真题 Python实现】数组拼接
- 560. 和为 K 的子数组-前缀和+暴力解法和前缀和+哈希表解法
- 1366. 通过投票对团队排名-数组统计选票+自定义插入排序
- Leetcode 643. 子数组最大平均数 I(网友思路)
- c++数组初始化‘0’
- HDU 4777 Rabbit Kingdom(树状数组)
- 说说js中使用for in遍历数组存在的bug