Segment Tree Implementation (Lazy Propagation)

Правка en4, от Iwaskid, 2017-02-03 03:36:49

Hi all, I am trying to code up a solution to the "Seating" problem in USACO January 2013 Gold, which uses a segment tree with lazy propagation. My code passes the first 2 test cases, but fails the rest. I have checked multiple times about my code but I don't see the problem.

#include<iostream>
#include<fstream>
#include<algorithm>
#include<assert.h>
#include<string>
#include<vector>
using namespace std;
int n, m;
int t;
vector<int> A;
vector<int> l0, r0, lazy0, lazy1,ans;

void build(int a,int l,int r) {
	if (r - l < 1) {
		l0[a] = 1;
		r0[a] = 1;
		ans[a] = 1;
		return;
	}
	l0[a] = r - l + 1;
	r0[a] = r - l + 1;
	ans[a] = r - l + 1;
	build(a * 2, l, (r + l) / 2);
	build(a * 2 + 1, (r + l) / 2 + 1, r);
}
void lazyupdate(int a,int l,int r) {
	assert(!(lazy0[a]==1&& lazy1[a]));
	if (lazy0[a]) {
		lazy0[a] = 0;
		l0[a] =ans[a]= r - l + 1;
		r0[a] = r - l + 1;
		if (l != r) { lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1; lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0; }
	}
	else if (lazy1[a]) {
		l0[a] = ans[a]=r0[a] = 0;
		if (l != r) { lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0; }
		lazy1[a] = 0;
	}
}
void updateint(int a, int l, int r) {
	int left = 2 * a, right = 2 * a + 1;
	l0[a] = ans[a] = r0[a] = 0;
	if (l0[left] == ((l + r) / 2 - l + 1)) {
		l0[a] = max(l0[a], max(l0[left], l0[left] + l0[right]));
	}
	else l0[a] = max(l0[a], l0[left]);
	if (r0[right] == (r - (l + r) / 2)) {
		r0[a] = max(r0[a], r0[right] + r0[left]);
	}
	else r0[a] = max(l0[a], r0[right]);
	ans[a] = max(r0[a], max(l0[a], r0[left] + l0[right]));
}
void update0(int i, int j,int a=1, int l=0, int r=n-1) {
	lazyupdate(a, l, r);
	if (j<l || i>r)return;
	
	if (l >= i&&r <= j) {
		l0[a] = r - l + 1;
		r0[a] =ans[a]= r - l + 1;
		if (l == r)return;
		lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1;
		lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0;
		return;
	}
	int left = 2 * a, right = 2 * a + 1;
	update0(i, j, left, l, (l + r) / 2);
	update0(i, j, right, (l + r) / 2 + 1, r);
	updateint(a, l, r);

}
void update1(int i, int j, int a = 1, int l = 0, int r = n - 1) {
	lazyupdate(a, l, r);
	if (j<l || i>r)return;

	if (l >= i&&r <= j) {
		l0[a] = 0;
		r0[a] = 0;
		ans[a] = 0;
		if (l == r)return;
		lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; 
		lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0;
		return;
	}
	int left = 2 * a, right = 2 * a + 1;
	update1(i, j, left, l, (l + r) / 2);
	update1(i, j, right, (l + r) / 2 + 1, r);
	updateint(a, l, r);
}
pair<int,int> getint(int num, int a = 1, int l = 0, int r = n - 1) {
	lazyupdate(a, l, r);
	if(l!=r)lazyupdate(2 * a, l, (l + r) / 2);
	if(l!=r)lazyupdate(2 * a + 1, (l + r) / 2 + 1, r);
	if (ans[a] == num&&r-l+1==num) {
		return pair<int, int>(l, r);
	}
	int left = 2 * a, right = 2 * a + 1;
	if (ans[left] >= num) {
		return getint(num, a * 2, l, (l + r) / 2);
	}

	if (r0[left] + l0[right] >= num&&r0[left]!=0) {
			int need = num - r0[left];
			pair<int, int> p1;
			p1.first = (l + r) / 2 - r0[left] + 1;
			p1.second = (l + r) / 2 + need;
			
			return p1;
	}
	if (ans[right]>=num) {
		return getint(num, a * 2 + 1, (l + r) / 2 + 1, r);
	}
	assert(0);
}
int main() {
	ifstream fin("seating.in");
	ofstream fout("seating.out");
	fin >> n >> m;
	l0, r0, lazy0, lazy1, ans;
	A.resize(n);
	l0.resize(4 * n); r0.resize(4 * n); lazy0.resize(4 * n); lazy1.resize(4 * n); ans.resize(4 * n);
	build(1, 0, n - 1);
	int res = 0;
	for (int i = 0; i < m; i++) {

		string stat;
		fin >> stat;
		if (stat[0] == 'A') {
			int add; fin >> add;
			if (ans[1] < add) {
				res++;
				continue;
			}
			pair<int, int> p = getint(add);
			update1(p.first, p.second);
		}
		else {
			int from, to; fin >> from >> to;
			from--; to--;
			update0(from, to);
		}
	}
	fout << res << endl;
	return 0;
}

In my segment tree, update0 updates a given range of values to 0,update1 updates a given range of values to 1, updateint updates the interval whenever some of its values have changed.getInt(add) gets the lowest position to insert the group of people. lazy0 andlazy1 stores respectively the lazy propagation for setting to 0 and setting to 1. Thank you so much for your help.

Теги c++, data structures, segment tree, lazy propagation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Iwaskid 2017-02-03 03:36:49 19
en3 Английский Iwaskid 2017-02-02 06:37:13 0 (published)
en2 Английский Iwaskid 2017-02-02 06:36:51 0 (saved to drafts)
en1 Английский Iwaskid 2017-02-02 06:35:00 4367 Initial revision (published)