hdu 4031 Attack(BIT)

acm.hdu.edu.cn/showproblem.php?pid=4031

　　一道树状数组的题目，当然，用线段树也是可以的。不过线段树的常数比较大，所以不建议在这题用。

　　题意：有一道1～N的防线。对于每一个防线单位，某个时间t₀被攻击过后，t₀+1~t₀+t-1的时间里的所有攻击都是成功的。在某些攻击过后会有查询，询问某个防线单位到目前为止受到了共多少次攻击。每攻击一次算一次单位时间，查询不算时间。

　　做法是用全部包含该被询问的防线单位的攻击次数减去被成功防御的攻击次数，因为这样做可以将统计的时间跳跃查找，从而降低复杂度。当然，最坏的情况是每个询问都由头搜索到尾，复杂度O(n^2)。根据运行时间，目测一组数据最多只有一个case会这样子。

　　因为一开始的时候树状数组写砸了，所以打了个暴力代码和随机数据来debug。浪费了不少时间。。。囧！最囧的是，原来在打暴力代码前已经改对了，不过没敢交。。TAT

随机数据生成代码：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <ctime>
 5 #include <algorithm>
 6 
 7 #define FILEPOS freopen("/home/scau_lyon/桌面/temp/in", "w", stdout)
 8 
 9 using namespace std;
10 
11 int main() {
12     int n = 1;
13 
14     FILEPOS;
15     srand(time(NULL));
16     printf("%d\n", n);
17     while (n--) {
18         int N = 20000; //rand() % 1000 + 9001;
19         int Q = 20000; //rand() % 1000 + 4001;
20         int t = rand() % 10 + 21;
21 
22         printf("%d %d %d\n", N, Q, t);
23         while (Q--) {
24             if (rand() % 20 <= 18) {
25                 int l = rand() % N + 1;
26                 int r = rand() % N + 1;
27 
28                 if (l > r) swap(l, r);
29                 printf("Atttack %d %d\n", l, r);
30             } else {
31                 printf("Query %d\n", rand() % N + 1);
32             }
33         }
34     }
35 
36     return 0;
37 }

AC代码及暴力代码：

View Code

  1 #define prog 1
  2 
  3 #if prog == 1
  4 
  5 #include <cstdio>
  6 #include <cstring>
  7 #include <algorithm>
  8 #include <cstdlib>
  9 
 10 const int maxn = 20005;
 11 
 12 struct BITree {
 13     int sum[maxn];
 14     int maxLen;
 15 
 16     void init() {
 17         memset(sum, 0, sizeof(int) * (maxLen + 1));
 18     }
 19 
 20     void posAdd(int x, int d) { // pos x add d
 21         while (x <= maxLen) {
 22             sum[x] += d;
 23             x += x & (-x);
 24         }
 25     }
 26 
 27     int preSum(int x) { // sum from 1 to x
 28         int ret = 0;
 29 
 30         while (x > 0) {
 31             ret += sum[x];
 32             x -= x & (-x);
 33         }
 34 
 35         return ret;
 36     }
 37 
 38     int segSum(int l, int r) { // sum from l to r
 39         return preSum(r) - preSum(l - 1);
 40     }
 41 } BIT;
 42 
 43 int posTime[maxn], defCnt[maxn], attL[maxn], attR[maxn];
 44 
 45 void deal(int N, int Q, int t) {
 46     BIT.maxLen = N;
 47     BIT.init();
 48 
 49     memset(posTime, 0, sizeof(int) * (N + 1));
 50     memset(defCnt, 0, sizeof(int) * (N + 1));
 51 
 52     char buf[10];
 53     int p, curTime = 0;
 54 
 55     for (int i = 0; i < Q; i++) {
 56         scanf("%s", buf);
 57         if (buf[0] == 'A') {
 58             scanf("%d%d", &attL[curTime], &attR[curTime]);
 59             if (attL[curTime] > attR[curTime]) std::swap(attL[curTime], attR[curTime]);
 60             BIT.posAdd(attL[curTime], 1);
 61             BIT.posAdd(attR[curTime] + 1, -1);
 62             curTime++;
 63         } else {
 64             scanf("%d", &p);
 65             while (posTime[p] < curTime) {
 66                 if (attL[posTime[p]] <= p && p <= attR[posTime[p]]) {
 67                     defCnt[p]++;
 68 //                    printf("t %d\n", posTime[p]);
 69                     posTime[p] += t - 1;
 70                 }
 71                 posTime[p]++;
 72             }
 73 //            printf("%d %d\n", BIT.preSum(p), defCnt[p]);
 74             printf("%d\n", BIT.preSum(p) - defCnt[p]);
 75         }
 76     }
 77 }
 78 
 79 
 80 int main() {
 81     int T;
 82     int N, Q, t;
 83 
 84     freopen("in", "r", stdin);
 85     freopen("out", "w", stdout);
 86     scanf("%d", &T);
 87     for (int C = 1; C <= T; C++) {
 88         printf("Case %d:\n", C);
 89         scanf("%d%d%d", &N, &Q, &t);
 90         deal(N, Q, t);
 91     }
 92 
 93     return 0;
 94 }
 95 
 96 #endif
 97 
 98 #if prog == 2
 99 
100 #include <cstdio>
101 #include <cstring>
102 #include <cstdlib>
103 
104 const int maxn = 20005;
105 
106 int attCnt[maxn], lastAtt[maxn];
107 
108 void init(int n) {
109     for (int i = 1; i <= n; i++) {
110         attCnt[i] = 0;
111         lastAtt[i] = -maxn;
112     }
113 }
114 
115 void attack(int l, int r, int coldTime, int curTime) {
116     for (int i = l; i <= r; i++) {
117         if (lastAtt[i] + coldTime <= curTime) {
118             lastAtt[i] = curTime;
119         } else {
120             attCnt[i]++;
121         }
122     }
123 }
124 
125 int main() {
126     int T;
127     int N, Q, t;
128 
129     freopen("in", "r", stdin);
130     freopen("cmp", "w", stdout);
131     scanf("%d", &T);
132     for (int C = 1; C <= T; C++) {
133         printf("Case %d:\n", C);
134         scanf("%d%d%d", &N, &Q, &t);
135 
136         int curTime = 0;
137 
138         init(N);
139         while (Q--) {
140             char buf[3];
141 
142             scanf("%s", buf);
143             if (buf[0] == 'A') {
144                 int l, r;
145 
146                 scanf("%d%d", &l, &r);
147                 attack(l, r, t, curTime);
148                 curTime++;
149             } else {
150                 int p;
151 
152                 scanf("%d", &p);
153                 printf("%d\n", attCnt[p]);
154             }
155         }
156     }
157 
158     return 0;
159 }
160 
161 #endif

——written by Lyon