菜鸡求助二维树状数组/kel
查看原帖
菜鸡求助二维树状数组/kel
376161
Phartial静月千阴楼主2022/2/17 18:53

rt,照着第一篇题解写的,样例一直过不去,菜鸡不会调,所以求助巨佬们

#include <iostream>

using namespace std;

const int kN = 2049;

int n, m;
char ch;
struct T {
  int b[kN][kN];

  void Add(int x, int y, int v) {
    for (; x <= n; x += x & -x) {
      for (; y <= m; y += y & -y) {
        b[x][y] += v;
      }
    }
  }
  int Query(int x, int y) {
    int s = 0;
    for (; x; x -= x & -x) {
      for (; y; y -= y & -y) {
        s += b[x][y];
      }
    }
    return s;
  }
} a[4];

void Add(int x, int y, int v) {
  a[0].Add(x, y, v), a[1].Add(x, y, v * x), a[2].Add(x, y, v * y), a[3].Add(x, y, v * x * y);
}
int Query(int x, int y) {
  return a[0].Query(x, y) * (x * y + x + y + 1) - a[1].Query(x, y) * (y + 1) - a[2].Query(x, y) * (x + 1) + a[3].Query(x, y);
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> ch >> n >> m;
  for (int v, x0, y0, x1, y1; cin >> ch >> x0 >> y0 >> x1 >> y1;) {
    if (ch == 'L') {
      cin >> v;
      ++x1, ++y1;
      Add(x0, y0, v), Add(x0, y1, -v), Add(x1, y0, -v), Add(x1, y1, v);
    } else {
      --x0, --y0;
      cout << Query(x1, y1) - Query(x1, y0) - Query(x0, y1) + Query(x0, y0) << '\n';
    }
  }
  return 0;
}
2022/2/17 18:53
加载中...