萌新求助二维树状数组!
查看原帖
萌新求助二维树状数组!
804607
rainygame楼主2023/5/14 13:18
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2049
#define lowbit(x) (x & -x)

int n, m, a, b, c, d, delta;
int c1[MAXN][MAXN], c2[MAXN][MAXN], c3[MAXN][MAXN], c4[MAXN][MAXN];
char ch;

void add(int x, int y, int z){
	for (int i(x); i<=n; i+=lowbit(i)){
		for (int j(y); j<=m; j+=lowbit(i)){
			c1[i][j] += z;
			c2[i][j] += z*x;
			c3[i][j] += z*y;
			c4[i][j] += z*x*y;
		}
	}
}

void add(int xa, int ya, int xb, int yb, int z){
	add(xa, ya, z);
  	add(xa, yb+1, -z);
  	add(xb+1, ya, -z);
  	add(xb+1, yb + 1, z);
}

long long ask(int x, int y){
	long long res(0);
  	for (int i(x); i; i-=lowbit(i)){
  		for (int j(y); j; j-=lowbit(j)) res += (x+1)*(y+1)*c1[i][j]-(y+1)*c2[i][j]-(x+1)*c3[i][j]+c4[i][j];
	}
  	return res;
}

long long ask(int xa, int xb, int ya, int yb){
	return ask(xb, yb) - ask(xb, ya-1) - ask(xa-1, yb) + ask(xa-1, ya-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 >> a >> b >> c >> d >> delta;
				add(a, b, c, d, delta);
				break;
			case 'k':
				cin >> a >> b >> c >> d;
				cout << ask(a, b, c, d) << '\n';
				break;
		}
	}
	
	return 0;
}

2023/5/14 13:18
加载中...