可爱萌新妺子刚学二维树状数组求调
查看原帖
可爱萌新妺子刚学二维树状数组求调
1347770
UnfortunatelyDead楼主2024/5/19 21:40

rt

#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <map>
#include <stack>
using namespace std;
#define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << x << '\n'
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch) {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
#define lowbit(x) (x & (-x))
const int N = 3333;
int t[4][N][N], n, m;
void add(int x, int y, int s) {
	for (int i = x; i <= n; i += lowbit(i)) {
		for (int j = y; j <= m; j += lowbit(j)) {
			t[0][i][j] += s;
			t[1][i][j] += s * i;
			t[2][i][j] += s * j;
			t[3][i][j] += s * i * j;
		}
	}  
}
int query(int x, int y) {
	int ans = 0;
	for (int i = x; i; i -= lowbit(i)) {
		for (int j = y; j; j -= lowbit(j)) {
			ans += t[0][i][j] * (x * y + x + y + 1) - t[1][i][j] * (y + 1) - t[2][i][j] * (x + 1) + t[3][i][j];
		}
	}
	return ans;
}
char Getchar() {
	char c = getchar();
	while (c != 'L' && c != 'k') {
		if (c == EOF) quit();
		c = getchar();
	}
	return c;
}
void solve() {
	read(n, m);
	while (1) {
		char c = Getchar(); int x1, y1, x2, y2, s;
		read(x1, y1, x2, y2);
		if (c == 'L') {
			read(s);
			add(x1, y1, s);
			add(x1, y2 + 1, -s);
			add(x2 + 1, y1, -s);
			add(x2 + 1, y2 + 1, s);
		} else {
			write(query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1), '\n');
		}
	}
}
signed main() {
	int t = 1;
	// t = read();
	while (t--) solve();
	return 0;
}

WA+MLE

2024/5/19 21:40
加载中...