【二维树状数组】样例过不了求调(悬关)
查看原帖
【二维树状数组】样例过不了求调(悬关)
804607
rainygame楼主2023/5/27 06:28

越调越乱。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 2049 
#define lowbit(x) (x & -x)

int n, m, x_1, y_1, x_2, y_2, v;
int t1[MAXN][MAXN], t2[MAXN][MAXN], t3[MAXN][MAXN], t4[MAXN][MAXN];
char ch;

void add(int x, int y, int v){
	int i(x), j(y);
	while (i <= n){
		while (j <= m){
			t1[i][j] += v;
			t2[i][j] += x*v;
			t3[i][j] += y*v;
			t4[i][j] += x*y*v;
			j += lowbit(j);
		}
		i += lowbit(i);
	}
}

void add(){
	add(x_1, y_1, v);
	add(x_2+1, y_2+1, v);
	add(x_2+1, y_1, -v);
	add(x_1, y_2+1, -v);
}

int query(int x, int y){
	int i(x), j(y), res(0);
	while (i){
		while (j){
			res += (x+1)*(y+1)*t1[i][j] - (y+1)*t2[i][j] - (x+1)*t3[i][j] + t4[i][j];
			j -= lowbit(j);
		}
		i -= lowbit(i);
	}
	return res;
}

int query(){
	return query(x_2, y_2)-query(x_2, y_1-1)-query(x_1-1, y_2)+query(x_1-1, y_1-1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	while (cin >> ch){
		switch (ch){
			case 'X':
				cin >> n >> m;
				break;
			case 'L':
				cin >> x_1 >> y_1 >> x_2 >> y_2 >> v;
				add();
				break;
			case 'k':
				cin >> x_1 >> y_1 >> x_2 >> y_2;
				cout << query() << '\n';
		}
	}
	
	return 0;
}

请好心人帮忙调一下。

2023/5/27 06:28
加载中...