菜鸡刚学二维树状数组AC on#1求助qwq
查看原帖
菜鸡刚学二维树状数组AC on#1求助qwq
716260
SegmentTree_楼主2024/1/18 00:29
#include<bits/stdc++.h>
using namespace std;
#define ll int
const int N = 2050;
int n, m, a, b, c, d;
char op;
ll x;
struct BIT{
	ll a[N][N];
	int lowbit(int x){
		return x & (-x);
	}
	void add(int x, int y, ll k){
		for (int i = x;i <= n;i += lowbit(i)){
			for (int j = y;j <= n;j += lowbit(j)) a[i][j] += k;
		}
	}
	ll sum(int x, int y){
		ll res = 0;
		for (int i = x;i;i -= lowbit(i)){
			for (int j = y;j;j -= lowbit(j)){
				res += a[i][j];
			}
		}
		return res;
	}
}t1, t2, t3, t4;
void addex(int x, int y, ll k){
	t1.add(x, y, k);
	t2.add(x, y, k * x);
	t3.add(x, y, k * y);
	t4.add(x, y, k * x * y);
}
void addexex(int a, int b, int c, int d, ll k){
	addex(a, b, k);
	addex(a, d + 1, -k);
	addex(c + 1, b, -k);
	addex(c + 1, d + 1, k);
}
ll sumex(int x, int y){
	return t1.sum(x, y) * (x * y + x + y + 1) -
			t2.sum(x, y) * (y + 1) -
			t3.sum(x, y) * (x + 1) +
			t4.sum(x, y);
}
ll sumexex(int a, int b, int c, int d){
	return sumex(c, d) - sumex(a - 1, c) - sumex(c, b - 1) + sumex(a - 1, b - 1);
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> op >> n >> m;
	while (cin >> op >> a >> b >> c >> d){
		if (op == 'L'){
			cin >> x;
			addexex(a, b, c, d, x);
		}
		else{
			cout << sumexex(a, b, c, d) << '\n';
		}
	}
	return 0;
} 
2024/1/18 00:29
加载中...