Brief description :

二维 RMQ。

Analyse :

..?

Area_Tree..

#include 
using namespace std;  
const int nn = 1024, ll = 1398101; //4 * nn * nn;

int Xl[ll], Xr[ll], Yl[ll], Yr[ll];
int Key[ll]; bool Close[ll];
int LeftDown[ll], LeftUp[ll], RightDown[ll], RightUp[ll];
int root, total; // Area-Tree
int xl, xr, yl, yr, v;
int n, m, q;

void _R(int &x){
	if (!((x & -x) == x)){
		do {
			x ^= x & -x;
		} while ((x & -x) != x);
		x <<= 1;
	}
}

void Open(int now){
	Close[LeftDown[now]] = Close[LeftUp[now]] = Close[RightDown[now]] = Close[RightUp[now]] = true;
             //.. key...#
	Close[now] = false;
}

void Build(int &now, int xl, int xr, int yl, int yr){
	now = total++, Xl[now] = xl, Xr[now] = xr, Yl[now] = yl, Yr[now] = yr;
	Key[now] = 0, Close[now] = true;
	
	//cout << xl << " " << xr << " " << yl << " " << yr << endl;
	
	if (!(xl == xr && yl == yr)){
		int xm = (xl + xr) / 2, ym = (yl + yr) / 2;
		Build(LeftDown[now], xl, xm, yl, ym);
		Build(LeftUp[now], xl, xm, ym+1, yr);
		Build(RightDown[now], xm+1, xr, yl, ym);
		Build(RightUp[now], xm+1, xr, ym+1, yr);
	}
}

int Query(int now){
	if (Close[now] || (xl <= Xl[now] && Xr[now] <= xr && yl <= Yl[now] && Yr[now] <= yr))
		return Key[now];
	
	int xm = (Xl[now] + Xr[now]) / 2, ym = (Yl[now] + Yr[now]) / 2, res = -1;
	
	if (xl <= xm && yl <= ym) res = max(res, Query(LeftDown[now]));
	if (xl <= xm && ym < yr && Key[LeftUp[now]] > res) res = max(res, Query(LeftUp[now]));
	if (xm < xr && yl <= ym && Key[RightDown[now]] > res) res = max(res, Query(RightDown[now]));
	if (xm < xr && ym < yr && Key[RightUp[now]] > res) res = max(res, Query(RightUp[now]));
	
	return res;
}

void Insert(int now){
	
	Key[now] = max(Key[now], v);
	
	if (xl <= Xl[now] && Xr[now] <= xr && yl <= Yl[now] && Yr[now] <= yr){
		Close[now] = true;
		return;
	}
	
	if (Close[now]) Open(now);
	
	int xm = (Xl[now] + Xr[now]) / 2, ym = (Yl[now] + Yr[now]) / 2;
	
	if (xl <= xm && yl <= ym) Insert(LeftDown[now]);
	if (xl <= xm && ym < yr) Insert(LeftUp[now]);
	if (xm < xr && yl <= ym) Insert(RightDown[now]);
	if (xm < xr && ym < yr) Insert(RightUp[now]);
}

int main(){
	//freopen("in.txt", "r", stdin);
	scanf("%d%d%d", &n, &m, &q), _R(n), _R(m);
	Build(root, 1, n, 1, m);
	int d, s, w, x, y;
	for (int i = 0; i < q; i ++){
		scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
		xl = x + 1, xr = x + d, yl = y + 1, yr = y + s, v = Query(root) + w;
		Insert(root);
	}
	
	xl = 1, xr = n, yl = 1, yr = m;
	printf("%d\n", Query(root));
}

.....
2_Dimension_Segment_Tree
...

#include 
using namespace std;  
const int nn = 1024, ll = 2047; //2 * nn - 1

struct Segment_Tree{
	int f[ll], s[ll];
	void Insert(int, int, int);
	void Query(int, int, int);
};

struct Two_Dimension_Segment_Tree{
	Segment_Tree f[ll], s[ll];
	void Insert(int, int, int);
	void Query(int, int, int);
} T;
int root;
int xl, xr, yl, yr, h;
int n, _m, q;


void Segment_Tree::Insert(int now, int l, int r){	
	
	f[now] = max(f[now], h);
	
	if (yl <= l && r <= yr){
		s[now] = max(s[now] , h); //f[now]);
		//s[now] = h; //#
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Insert(now, l, m);
		if (m < yr) Insert(now+1, m+1, r);
	}
}

void Segment_Tree::Query(int now, int l, int r){
	if (yl <= l && r <= yr){
		h = max(h, f[now]);
	}
	else {
		h = max(h, s[now]);
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Query(now, l, m);
		if (m < yr) Query(now+1, m+1, r);
	}
} 


void Two_Dimension_Segment_Tree::Insert(int now, int l, int r){
	
	f[now].Insert(root, 1, _m);
	
	if (xl <= l && r <= xr){
		s[now].Insert(root, 1, _m);
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Insert(now, l, m);
		if (m < xr) Insert(now+1, m+1, r);
	}
}

void Two_Dimension_Segment_Tree::Query(int now, int l, int r){
	if (xl <= l && r <= xr){
		f[now].Query(root, 1, _m);
	}
	else {
		s[now].Query(root, 1, _m);
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Query(now, l, m);
		if (m < xr) Query(now+1, m+1, r);
	}
}




int main(){
	//freopen("in.txt", "r", stdin);
	scanf("%d%d%d", &n, &_m, &q); root = 1;
	int d, s, w, x, y;
	for (int i = 0; i < q; i ++){
		scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
		xl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;
		T.Insert(root, 1, n);
	}
	
	xl = 1, xr = n, yl = 1, yr = _m, T.Query(root, 1, n);
	printf("%d\n", h);
}

#include 
using namespace std;  
const int nn = 1024, ll = 2047; //2 * nn - 1

struct Segment_Tree{
	int f[ll], s[ll];
	void Insert(int, int, int);
	void Query(int, int, int);
};

struct Two_Dimension_Segment_Tree{
	Segment_Tree f[ll], s[ll];
	void Insert(int, int, int);
	void Query(int, int, int);
} T;
int root;
int xl, xr, yl, yr, h;
int n, m, q;


void Segment_Tree::Insert(int now, int l, int r){	
	
	f[now] = max(f[now], h);
	
	if (yl <= l && r <= yr){
		s[now] = max(s[now] , h); //s[now] = h; //#
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Insert(now, l, m);
		if (m < yr) Insert(now+1, m+1, r);
	}
}

void Segment_Tree::Query(int now, int l, int r){
	if (yl <= l && r <= yr){
		h = max(h, f[now]);
	}
	else {
		h = max(h, s[now]);
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Query(now, l, m);
		if (m < yr) Query(now+1, m+1, r);
	}
} 


void Two_Dimension_Segment_Tree::Insert(int now, int l, int r){
	
	f[now].Insert(root, 1, m);
	
	if (xl <= l && r <= xr){
		s[now].Insert(root, 1, m);
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Insert(now, l, m);
		if (m < xr) Insert(now+1, m+1, r);
	}
}

void Two_Dimension_Segment_Tree::Query(int now, int l, int r){
	if (xl <= l && r <= xr)
		f[now].Query(root, 1, m);
	else {
		s[now].Query(root, 1, m);
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Query(now, l, m);
		if (m < xr) Query(now+1, m+1, r);
	}
}




int main(){
	//freopen("in.txt", "r", stdin);
	scanf("%d%d%d", &n, &m, &q); root = 1;
	int d, s, w, x, y;
	for (int i = 0; i < q; i ++){
		scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
		xl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;
		T.Insert(root, 1, n);
	}
	xl = 1, xr = n, yl = 1, yr = m, T.Query(root, 1, n);
	printf("%d\n", h);
}


/*
 f >= s
 f >= f[l], f[r];...
 s <= s[l], s[r];...
 s != 0 ...(.. == s.)
 */

#include 
using namespace std;  
const int nn = 1024, ll = 2048; //2 * nn

struct Segment_Tree{
	int key[ll]; bool close[ll];
	void Open(int);
	void Insert(int, int, int);
	void Query(int, int, int);
};

struct Two_Dimension_Segment_Tree{
	Segment_Tree f[ll], s[ll];
	void Insert(int, int, int);
	void Query(int, int, int);
} T;
int root;
int xl, xr, yl, yr, h;
int n, m, q;



void Segment_Tree::Open(int now){
	int left = now << 1, right = left + 1;
	key[left] = key[right] = key[now];
	close[left] = close[right] = true;
	close[now] = false;
}

void Segment_Tree::Insert(int now, int l, int r){	
	if (yl <= l && r <= yr){
		key[now] = max(key[now], h);
		close[now] = true;
	}
	else {
		if (close[now]) Open(now);
		key[now] = max(key[now], h);
		
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Insert(now, l, m);
		if (m < yr) Insert(now+1, m+1, r);
	}
}

void Segment_Tree::Query(int now, int l, int r){
	if (close[now] || yl <= l && r <= yr){
		h = max(h, key[now]);
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Query(now, l, m);
		if (m < yr) Query(now+1, m+1, r);
	}
} 


void Two_Dimension_Segment_Tree::Insert(int now, int l, int r){
	
	f[now].Insert(root, 1, m);
	
	if (xl <= l && r <= xr){
		s[now].Insert(root, 1, m);
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Insert(now, l, m);
		if (m < xr) Insert(now+1, m+1, r);
	}
}

void Two_Dimension_Segment_Tree::Query(int now, int l, int r){
	if (xl <= l && r <= xr)
		f[now].Query(root, 1, m);
	else {
		s[now].Query(root, 1, m);
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Query(now, l, m);
		if (m < xr) Query(now+1, m+1, r);
	}
}




int main(){
	freopen("in.txt", "r", stdin);
	scanf("%d%d%d", &n, &m, &q); root = 1;
	int d, s, w, x, y;
	for (int i = 0; i < q; i ++){
		scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
		xl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;
		T.Insert(root, 1, n);
	}
	xl = 1, xr = n, yl = 1, yr = m, h = 0, T.Query(root, 1, n);
	printf("%d\n", h);
}


/*
 f >= s
 f >= f[l], f[r];...
 s <= s[l], s[r];...
 s != 0 ...(.. == s.)
 */

//。。!!!..

#include 
using namespace std;  
const int nn = 1024, ll = 2048; //2 * nn - 1


struct Event{
	int now, l, r, h;
	Event() {} 
	Event(int a, int b, int c, int d) :now(a), l(b), r(c), h(d){}
};

struct Segment_Tree{
	int key[ll]; bool close[ll];
	void Open(int);
	void Insert(int, int, int);
	void Query(int, int, int);
};

struct Two_Dimension_Segment_Tree{
	Segment_Tree key[ll]; bool close[ll]; Event delay[ll];
	void Open(int);
	void Insert(int, int, int);
	void Query(int, int, int);
} T;
int root;
int xl, xr, yl, yr, h;
int n, m, q;



void Segment_Tree::Open(int now){
	int left = now << 1, right = left + 1;
	key[left] = key[right] = key[now];
	close[left] = close[right] = true;
	close[now] = false;
}

void Segment_Tree::Insert(int now, int l, int r){		
	if (yl <= l && r <= yr){
		key[now] = max(key[now], h);
		close[now] = true;
	}
	else {
		if (close[now]) Open(now);
		key[now] = max(key[now], h);
		
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Insert(now, l, m);
		if (m < yr) Insert(now+1, m+1, r);
	}
}

void Segment_Tree::Query(int now, int l, int r){
	if (close[now] || yl <= l && r <= yr){
		h = max(h, key[now]);
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (yl <= m) Query(now, l, m);
		if (m < yr) Query(now+1, m+1, r);
	}
} 

void Two_Dimension_Segment_Tree::Open(int now){
	int left = now << 1, right = left + 1;
	
	int t1 = yl, t2 = yr, t3 = h;
	yl = delay[now].l, yr = delay[now].r, h = delay[now].h;
	key[left].Insert(root, 1, m), key[right].Insert(root, 1, m);
	yl = t1, yr = t2, h = t3;	
	
	delay[left] = delay[right] = delay[now];
	close[left] = close[right] = true;
	close[now] = false;
}


void Two_Dimension_Segment_Tree::Insert(int now, int l, int r){
	if (xl <= l && r <= xr){
		key[now].Insert(root, 1, m);
		delay[now] = Event(now, yl, yr, h);
		close[now] = true;
	}
	else {
		if (close[now]) Open(now);
		key[now].Insert(root, 1, m);
		
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Insert(now, l, m);
		if (m < xr) Insert(now+1, m+1, r);
	}
}

void Two_Dimension_Segment_Tree::Query(int now, int l, int r){
	if (close[now] || xl <= l && r <= xr){
		key[now].Query(root, 1, m);
	}
	else {
		int m = (l + r) / 2; now <<= 1;
		if (xl <= m) Query(now, l, m);
		if (m < xr) Query(now+1, m+1, r);
	}
}




int main(){
	//freopen("in.txt", "r", stdin);
	scanf("%d%d%d", &n, &m, &q); root = 1;
	int d, s, w, x, y;
	for (int i = 0; i < q; i ++){
		scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
		xl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;
		T.Insert(root, 1, n);
	}
	xl = 1, xr = n, yl = 1, yr = m, h = 0, T.Query(root, 1, n);
	printf("%d\n", h);
}


/*
 f >= s
 f >= f[l], f[r];...
 s <= s[l], s[r];...
 s != 0 ...(.. == s.)
 */

External link :

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1513
http://www.main.edu.pl/user.phtml?op=zadania&c=1300

Posted by xiaodao
Category: 日常