求debug
  • 板块学术版
  • 楼主_luanyi_
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/11/3 10:03
  • 上次更新2023/11/5 09:08:56
查看原帖
求debug
300313
_luanyi_楼主2020/11/3 10:03

这是一段关于二维线段树的代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4040;
#define int long long





int tree[maxn][maxn], lazy[maxn][maxn]; 
int n, q;
void push_up (int rtx, int rty) {
	tree[rtx][rty] = tree[rtx << 1][rty << 1] + tree[rtx << 1][rty << 1 | 1] + tree[rtx << 1 | 1][rty << 1] + tree[rtx << 1 | 1][rty << 1 | 1];
}
void push_down (int xl, int xr, int yl, int yr, int rtx, int rty) {
	if ((xl != xr || yl != yr) && lazy[rtx][rty]) {
		int midx = (xl + xr) >> 1;
		int midy = (yl + yr) >> 1;
		tree[rtx << 1][rty << 1] += lazy[rtx][rty] * (midx - xl + 1) * (midy - yl + 1);
		tree[rtx << 1][rty << 1 | 1] += lazy[rtx][rty] * (midx - xl + 1) * (yr - midy);
		tree[rtx << 1 | 1][rty << 1] += lazy[rtx][rty] * (xr - midx) * (midy - yl + 1);
		tree[rtx << 1 | 1][rty << 1 | 1] += lazy[rtx][rty] * (xr - midx) * (yr - midy);
		lazy[rtx << 1][rty << 1] += lazy[rtx][rty];
		lazy[rtx << 1][rty << 1 | 1] += lazy[rtx][rty];
		lazy[rtx << 1 | 1][rty << 1] += lazy[rtx][rty];
		lazy[rtx << 1 | 1][rty << 1 | 1] += lazy[rtx][rty];
	}
	lazy[rtx][rty] = 0;
}
void update (int xL, int xR, int yL, int yR, int xl, int xr, int yl, int yr, int rtx, int rty, int x) {
	if (xL <= xl && xr <= xR && yL <= yl && yr <= yR) {
		tree[rtx][rty] += (xr - xl + 1) * (yr - yl + 1) * x;
		lazy[rtx][rty] += x;
	}
	else {
		int midx = (xl + xr) >> 1;
		int midy = (yl + yr) >> 1;
		if (xL <= midx && yL <= midy) update (xL, xR, yL, yR, xl, midx, yl, midy, rtx << 1, rty << 1, x);
		if (xL <= midx && midy < yR) update (xL, xR, yL, yR, xl, midx, midy + 1, yr, rtx << 1, rty << 1 | 1, x);
		if (midx < xR && yL <= midy) update (xL, xR, yL, yR, midx + 1, xr, yl, midy, rtx << 1 | 1, rty << 1, x);
		if (midx < xR && midy < yR) update (xL, xR, yL, yR, midx + 1, xr, midy + 1, yr, rtx << 1 | 1, rty << 1 | 1, x);
		push_up (rtx, rty);
	}
}
int query (int xL, int xR, int yL, int yR, int xl, int xr, int yl, int yr, int rtx, int rty) {
	if (xL <= xl && xr <= xR && yL <= yl && yr <= yR) return tree[rtx][rty];
	push_down (xl, xr, yl, yr, rtx, rty);
	int ans = 0;
	int midx = (xl + xr) >> 1;
	int midy = (yl + yr) >> 1;
	if (xL <= midx && yL <= midy) ans += query (xL, xR, yL, yR, xl, midx, yl, midy, rtx << 1, rty << 1);
	if (xL <= midx && midy < yR) ans += query (xL, xR, yL, yR, xl, midx, midy + 1, yr, rtx << 1, rty << 1 | 1);
	if (midx < xR && yL <= midy) ans += query (xL, xR, yL, yR, midx + 1, xr, yl, midy, rtx << 1 | 1, rty << 1);
	if (midx < xR && midy < yR) ans += query (xL, xR, yL, yR, midx + 1, xr, midy + 1, yr, rtx << 1 | 1, rty << 1 | 1);
	return ans;
}




signed main () {
	cin >> n >> q;
	while (q--) {
		string s;
		cin >> s;
		if (s == string ("addpoint")) {
			int x, y, num;
			cin >> x >> y >> num;
			update (x, x, y, y, 1, n, 1, n, 1, 1, num);
		}
		if (s == string ("addarea")) {
			int xl, xr, yl, yr, num;
			cin >> xl >> yl >> xr >> yr >> num;
			update (xl, xr, yl, yr, 1, n, 1, n, 1, 1, num);
		}
		if (s == string ("querypoint")) {
			int x, y;
			cin >> x >> y;
			cout << query (x, x, y, y, 1, n, 1, n, 1, 1) << endl;
		}
		if (s == string ("queryareasum")) {
			int xl, xr, yl, yr;
			cin >> xl >> yl >> xr >> yr;
			cout << query (xl, xr, yl, yr, 1, n, 1, n, 1, 1) << endl;
		}
	}
	return 0;
}

样例输入

4 5
addpoint 2 2 5
addarea 1 2 3 4 6
querypoint 2 2
addpoint 2 3 7
queryareasum 1 1 4 4

样例输出

11
66

有谁帮我指出一下问题吗,万分感谢!

2020/11/3 10:03
加载中...