本文主要是介绍hdu 4031 Attack(树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：hdu 4031 Attack
题目大意：有一个长为n的长城，进行q次操作，d为防护罩的冷却时间，Attack表示区间a-b的墙将在1秒后受到攻击，
询问表示计算第a块墙受到攻击的次数，被防护罩抵消的不算。
解题思路：树状数组，更新区间查询点，每次攻击区间a-b时，只要进行add（a，1）； add（b+1， -1）；然后第i堵墙受到的总攻击次数即为sum（i）。实际受到攻击的次数=总攻击次数-防护次数。防护次数的计算是将每次攻击的区间记录下来，然后枚举被抵挡的次数。
#include <stdio.h>
#include <string.h>const int N = 20005;int n, q, d, ti, v[N], l[N], r[N], cnt[N], rec[N];void init() {scanf("%d%d%d", &n, &q, &d);ti = 0;memset(cnt, 0, sizeof(cnt));memset(rec, 0, sizeof(rec));memset(v, 0, sizeof(v));memset(l, 0, sizeof(l));memset(r, 0, sizeof(r));
}void add(int x, int val) {while (x <= n) {v[x] += val;x += (x & (-x));}
}int sum(int x) {int ans = 0;while (x > 0) {ans += v[x];x -= (x &(-x));}return ans;
}void solve() {int a, b;char o[10];for (int i = 0; i < q; i++) {scanf("%s", o);if (o[0] == 'A') {scanf("%d%d", &a, &b);add(a, 1); add(b+1, -1);l[ti] = a, r[ti] = b;ti++;} else {scanf("%d", &a);for (int j = rec[a]; j < ti; j++) if (l[j] <= a && r[j] >= a) {rec[a] = j + d;cnt[a]++;j += d - 1;}printf("%d\n", sum(a) - cnt[a]);}}
}int main() {int cas;scanf("%d", &cas);for (int i = 1; i <= cas; i++) {printf("Case %d:\n", i);init();solve();}return 0;
}
这篇关于hdu 4031 Attack(树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
