帮帮蒟蒻
查看原帖
帮帮蒟蒻
461359
huangrenheluogu楼主2023/11/17 08:47

明天就要 NOIP 了,帮蒟蒻调一下二维树状数组为什么 RE。

谢谢。

NOIP2023 rp++

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2505;
char o;
int n, m, a, b, c, d, k, e[5][N][N];
inline void in(){
	if(o != 'X' && o != 'k' && o != 'L') o = getchar();
}
inline int lowbit(int x){
	return x & -x;
}
inline void add(int x, int y, int val, int op){
	for(int i = x; i <= n; i += lowbit(i)){
		for(int j = y; j <= m; j += lowbit(j)){
			e[op][i][j] += val;
		}
	}
}
inline void Add(int x, int y, int val){
	add(x, y, val, 0);
	add(x, y, val * x, 1);
	add(x, y, val * y, 2);
	add(x, y, val * x * y, 3);
}
inline void upd(int a, int b, int c, int d, int val){
	Add(a, b, val);
	Add(a, d + 1, -val);
	Add(c + 1, b, -val);
	Add(c + 1, d + 1, val);
}
inline int get(int x, int y, int op){
	int res = 0;
	for(int i = x; i; i -= lowbit(i)){
		for(int j = x; j ; j -= lowbit(j)){
			res += e[op][i][j];
		}
	}
	return res;
}
inline int petr(int x, int y){
	int res = 0;
	res += get(x, y, 0) * (x + 1) * (y + 1);
	res -= get(x, y, 1) * (y + 1);
	res -= get(x, y, 2) * (x + 1);
	res += get(x, y, 3);
	return res;	
}
inline int ans(int a, int b, int c, int d){
	return petr(c, d) - petr(a - 1, d) - petr(c, b - 1) + petr(a - 1, b - 1);
}
signed main(){
	in();
	scanf("%lld%lld", &n, &m);
	in();
	while(scanf("%c", &o) != EOF){
		in();
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		if(o == 'L'){
			scanf("%lld", &k);
			upd(a, b, c, d, k);
		}
		else printf("%lld\n", ans(a, b, c, d));
	}
	return 0;
}
/*
X 3 3
L 1 1 3 3 4
k 1 1 3 3
*/
2023/11/17 08:47
加载中...