这是一道二位BIT的版,但是wtcl仍然有疑问。
疑问:树状数组部分。
正解:
struct BIT {
int tr[2505][2505];
int lowbit(int x) {return x&-x;}
void update(int x, int y, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
tr[i][j] += k;
}
}
}
int query(int x, int y) {
int sum = 0;
for (int i = x; i >= 1; i -= lowbit(i)) {
for (int j = y; j >= 1; j -= lowbit(j)) {
sum += tr[i][j];
}
}
return sum;
}
} tra, trb, trc, trd;
错解:
struct BIT {
int tr[2505][2505];
int lowbit(int x) {return x&-x;}
void update(int i, int j, int x) {
for (; i <= n; i += lowbit(i)) {
for (; j <= m; j += lowbit(j)) {
tr[i][j] += x;
}
}
}
int query(int i, int j) {
int sum = 0;
for (; i >= 1; i -= lowbit(i)) {
for (; j >= 1; j -= lowbit(j)) {
sum += tr[i][j];
}
}
return sum;
}
} tra, trb, trc, trd;
显而易见的,直接用参数调整不行,一定要用 i,j 去循环遍历。
输入本题样例,正解输出 12,错解输出 -4。
试过好多遍了,当两份代码仅剩树状数组不同的时候,错了。所以我猜测是树状数组的问题。
给我整疑惑了,求求大神帮助。
贴个完整代码吧,谁知道万一是别的地方写太丑了所以影响了:code