树状数组求调
查看原帖
树状数组求调
801371
Midnight_szx楼主2023/5/14 18:45
#include<iostream>
#include<algorithm>
#include<cstdio>
#define lowbit(x) ((x) & - (x))
#define int long long
using namespace std;
int t1[2050][2050], t2[2050][2050], t3[2050][2050], t4[2050][2050];
int n, m;
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)) {
	    	t1[i][j] = t1[i][j] + k;
	    	t2[i][j] = t2[i][j] + x * k;
	    	t3[i][j] = t3[i][j] + y * k;
	    	t4[i][j] = t4[i][j] + x * y * k;
		}
} 
int query(int x, int y) { 
	int ans = 0;
	for(int i = x; i > 0; i -= lowbit(i)) 
	    for(int j = y; j > 0; j -= lowbit(j)) 
	    	ans = ans + (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] - (x + 1) * t3[i][j] + t4[i][j];
	return ans;
}
signed main() {
	std::ios::sync_with_stdio(0);
	char op[2];
	scanf("%s", op);
	cin>>n>>m;
	while(scanf("%s", op) != EOF) {
		int a, b, c, d, cxk;
		cin>>a>>b>>c>>d;
		if(op[0] == 'L') {
			cin>>cxk;
			update(a, b, cxk);
			update(c + 1, d + 1, cxk);
			update(a, d + 1, cxk * (-1));
			update(c + 1, b, cxk * (-1));
		}
		if(op[0] == 'k') 
		    cout<<query(c, d) + query(a - 1, b - 1) - query(a - 1, d) - query(c, b - 1)<<'\n';
	}
	return 0;
}
2023/5/14 18:45
加载中...