求助二维线段树
查看原帖
求助二维线段树
323989
Vector_Mingfan楼主2021/12/22 23:08
#include <cstdio>
#include <iostream>
#include <algorithm>
// #pragma GCC optimize(3)
#define maxn 1010
#define slu ((o << 2) + 1)
#define sru ((o << 2) + 2)
#define sld ((o << 2) + 3)
#define srd ((o << 2) + 4)
#define midx ((l + r) >> 1)
#define midy ((u + d) >> 1)
using namespace std;
struct segtree {
  int maxx, tag;
} tree[maxn * maxn * 10];
inline int read() {
   char ch = getchar();
   int f = 0, w = 1;
   while(ch < '0' || ch > '9') {
     if(ch == '-') w = -1;
     ch = getchar();
   }
   while(ch >= '0' && ch <= '9') {
     f = f * 10 + ch - '0',
     ch = getchar();
   }
   return f * w;
}
inline void write(int s) {
   int k = 0, len = 0;
   if (s == 0)
    putchar('0');
   while (s) {
     k = k * 10 + s % 10;
     s /= 10;
     len++ ;
   }
   for (int i = 0;i < len;i++) {
     putchar(k % 10 + '0');
     k /= 10;
   }
}
inline void build_tree(int l, int r, int u, int d, int o) {
	tree[o].tag = 0;
	if (l == r && u == d) {
		tree[o].maxx = 0;
		return;
	}
	build_tree(l, midx, u, midy, slu);
	tree[o].maxx = max(tree[o].maxx, tree[slu].maxx);
	if (l != r) {
		build_tree(midx + 1, r, u, midy, sru);
		tree[o].maxx = max(tree[o].maxx, tree[sru].maxx);
		if (u != d) {
			build_tree(midx + 1, r, midy + 1, d, srd);
			tree[o].maxx = max(tree[o].maxx, tree[srd].maxx);
		}
	}
	if (u != d) {
		build_tree(l, midx, midy + 1, d, sld);
		tree[o].maxx = max(tree[o].maxx, tree[sld].maxx);
	}
	return ;
}
inline void push_down(int l, int r, int u, int d, int o) {
	if (!tree[o].tag) return;
	tree[slu].maxx = tree[o].tag;
	tree[slu].tag = tree[o].tag;
	if (l != r) {
		tree[sru].maxx = tree[o].tag;
		tree[sru].tag = tree[o].tag;
      
		if(u != d) {
    	tree[srd].maxx = tree[o].tag;
    	tree[srd].tag = tree[o].tag;
    	}
	}
	if (u != d) {
    	tree[sld].maxx = tree[o].tag;
    	tree[sld].tag = tree[o].tag;
	}
	tree[o].tag = 0;
	return ;
}
inline void update_tree(int ql, int qr, int qu, int qd, int l, int r, int u, int d, int o, int add) { 
	if (l >= ql && r <= qr && u >= qu && d <= qd) {
		tree[o].maxx = add;
		tree[o].tag = add;
		return;
	}
    push_down(l, r, u, d, o);
    if (ql <= midx) {
		if (qu <= midy) {
			update_tree(ql, qr, qu, qd, l, midx, u, midy, slu, add);
			tree[o].maxx = max(tree[slu].maxx, tree[o].maxx);
		}
		if(qd > midy && u != d) {
			update_tree(ql, qr, qu, qd, l, midx, midy + 1, d, sld, add);
			tree[o].maxx = max(tree[sld].maxx, tree[o].maxx);
		}
	}
	if (qr > midx && l!=r) {
		if (qu <= midy) {
			update_tree(ql, qr, qu, qd, midx + 1, r, u, midy, sru, add);
			tree[o].maxx = max(tree[sru].maxx, tree[o].maxx);
		}
		if (qd > midy && u != d) {
			update_tree(ql, qr, qu, qd, midx + 1, r, midy + 1, d, srd, add);
			tree[o].maxx = max(tree[srd].maxx, tree[o].maxx);
		}
	}
	return ;
}
inline int query_tree(int ql, int qr, int qu, int qd, int l, int r, int u, int d, int o) {
	if (l >= ql && r <= qr && u >= qu && d <= qd) return tree[o].maxx;
	push_down(l, r, u, d, o);
	int ans = -1;
	if (ql <= midx) {
		if (qu <= midy) ans = max(query_tree(ql, qr, qu, qd, l, midx, u, midy, slu), ans);
		if (qd > midy && u != d) ans=max(query_tree(ql, qr, qu, qd, l, midx, midy + 1, d, sld), ans);
	}
	if (qr > midx) {
		if (l != r) {
			if (qu <= midy) ans = max(query_tree(ql, qr, qu, qd, midx + 1, r, u, midy, sru), ans);
			if (qd > midy && u != d) ans = max(query_tree(ql, qr, qu, qd, midx + 1, r, midy + 1, d, srd), ans);
		}
	}
    return ans;
}
int main() {
	int D, S, N;
	D = read();
	S = read();
	N = read();
	while (N--) {
		int d, s, h, x, y;
		d = read(); s = read(); h = read(); x = read(); y = read();
		int add = query_tree(x + 1, x + d, y + 1, y + s, 1, D, 1, S, 0) + h;
		update_tree(x + 1, x + d, y + 1, y + s, 1, D, 1, S, 0, add);
	}
	write(query_tree(1, D, 1, S, 1, D, 1, S, 0) );
//	printf("%d\n", query_tree(1, D, 1, S, 1, D, 1, S, 0));
	return 0;
}

超时五个点

2021/12/22 23:08
加载中...