Posted in Segment Tree

POJ 2528

8/18/2017
Problem: http://poj.org/problem?id=2528
Solution: Segment tree, obviously. But since there’re 10^7 bricks, segment tree
only would bring up a MLE. That’s why we are using hashing: if no
endpoints of posters lie on segment a-b, it doesn’t really matter how
long this segment is. We can simply map it to a segment of length 2.
Note: In regard to the expression “a||b”, if a is already true then b would not
be checked. That’s where I spent two days debugging..


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

struct poster {
	int l, r;
} p[10100];

int x[20200] = {0};
int hash[10000010] = {0};
int nodecnt = 0;

struct node {
	int l, r;
	bool c;
	node *pl, *pr;
};

node tree[1000005];

void build (node *root, int l, int r) {
	root->c = false;
	root->l = l;
	root->r = r;
	if (l == r) {
		return;
	}
	nodecnt++;
	root->pl = tree + nodecnt;
	nodecnt++;
	root->pr = tree + nodecnt;
	int mid = (l + r) / 2;
	build(root->pl, l, mid);
	build(root->pr, mid + 1, r);
}

bool post (node *root, int l, int r) {
	// cout << root->l << ' ' << root->r << ' ' << root->c << endl;
	if (root->c) {
		return false;
	}
	if (root->l == l && root->r == r) {
		root->c = true;
		return true;
	}
	bool b = false;
	int mid = (root->l + root->r) / 2;
	if (r <= mid) {
		b = post(root->pl, l, r);
	} else if (l > mid) {
		b = post(root->pr, l, r);
	} else {
		bool b1 = post(root->pl, l, mid);
		bool b2 = post(root->pr, mid + 1, r);
		b = b1 || b2;
	}
	if (root->pl->c && root->pr->c) {
		root->c = true;
	}
	return b;
}

int main() {
	int c;
	scanf("%d", &c);
	while (c--) {
		memset(x, 0, sizeof(x));
		memset(hash, 0, sizeof(hash));
		memset(p, 0, sizeof(p));
		memset(tree, 0, sizeof(tree));
		nodecnt = 0;
		int n;
		scanf("%d", &n);
		// cout << n << endl;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &p[i].l, &p[i].r);
			x[cnt++] = p[i].l;
			x[cnt++] = p[i].r;
		} 
		sort(x, x + cnt);
		cnt = unique(x, x + cnt) - x;
//		for (int i = 0; i < cnt; i++) {
//			cout << x[i] << ' ';
//		}
		int no = 0;
		for (int i = 0; i < cnt; i++) {
//			cout << no << ' ';
			hash[x[i]] = no;
			if (i < cnt - 1) {
				if (x[i + 1] - x[i] == 1) {
					no++;
				} else {
					no += 2;
				}
			}
		}
		build(tree, 0, no);
		int ans = 0;
		for (int i = n - 1; i >= 0; i--) {
			// cout << hash[p[i].l] << ' ' << hash[p[i].r] << endl; 
			if (post(tree, hash[p[i].l], hash[p[i].r])) {
				ans++;
				// cout << i << endl;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Posted in Segment Tree

POJ 4368 A Simple Problem with Integers

8/11/2017
Problem: http://poj.org/problem?id=3468
Solution: Record the sum for each segment. For time efficiency, here we do not
add immediately after an “add” operation. Instead, if reaching a
complete segment, simply record the inc value onto that exact point.
It would only be added to the individual points beneath when part of
the segment is queried.


#include<iostream>
#include<cstdio>
using namespace std;
int nodecnt = 0;

struct node{
	int l, r;
	node *pl, *pr;
	long long sum;
	long long inc;
};

node tree[200010];

void build (node *root, int l, int r) {
	root->l = l;
	root->r = r;
	root->sum = root->inc = 0;
	if (l == r) {
		return;
	}
	nodecnt++;
	root->pl = tree + nodecnt;
	nodecnt++;
	root->pr = tree + nodecnt;
	int mid = (l + r) / 2;
	build(root->pl, l, mid);
	build(root->pr, mid + 1, r);
}

void insert (node *root, int i, int v) {
	if (root->l == i && root->r == i) {
		root->sum = v;
		return;
	}
	root->sum += v;
	int mid = (root->l + root->r) / 2;
	if (i <= mid) {
		insert(root->pl, i, v);
	} else {
		insert(root->pr, i, v);
	}
}

void add (node *root, int l, int r, long long c) {
	// cout << l << ' ' << r << ' ' << c << endl;
	if (root->l == l && root->r == r) {
		root->inc += c;
		return;
	}
	root->sum += c * (r - l + 1);
	int mid = (root->l + root->r) / 2;
	if (r <= mid) {
		add (root->pl, l, r, c);
	} else if (l > mid) {
		add (root->pr, l, r, c);
	} else {
		add (root->pl, l, mid, c);
		add (root->pr, mid + 1, r, c);
	}
}

long long search (node *root, int l, int r) {
	// cout << l << ' ' << r << endl;
	if (root->l == l && root->r == r) {
		return root->sum + root->inc * (r - l + 1);
	}
	root->sum += (root->r - root->l + 1) * root->inc;
	int mid = (root->l + root->r) / 2;
	add (root->pl, root->l, mid, root->inc);
	add (root->pr, mid + 1, root->r, root->inc);
	root->inc = 0;
	if (r <= mid) {
		return search(root->pl, l, r);
	} else if (l > mid) {
		return search(root->pr, l, r);
	} else {
		return search(root->pl, l, mid) + search(root->pr, mid + 1, r);
	}
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	build(tree, 1, n);
	for (int i = 1; i <= n; i++) {
		int tmp;
		scanf("%d", &tmp);
		insert(tree, i, tmp);
	}
	for (int i = 1; i <= q; i ++) {
		char ch;
		cin >> ch;
		// scanf("%c", &ch);
		if (ch == 'Q') {
			int a, b;
			scanf("%d%d", &a, &b);
			printf("%lld\n", search(tree, a, b));
		} else {
			int a, b;
			long long c;
			scanf("%d%d%lld", &a, &b, &c);
			add(tree, a, b, c);
		}
	}
	return 0;
}


Posted in ACM-ICPC, Segment Tree

POJ 3264 Balanced Lineup

8/11/2017
Problem: http://poj.org/problem?id=3264
Solution: Record the max and min value for each segment.


#include<iostream>
#include<climits>
#include<cmath>
#include<cstdio>
using namespace std;
int mi = INT_MAX;
int ma = INT_MIN;

struct node{
	int l, r;
	int max;
	int min;
};

node t[800005] = {0};

void build (int root, int l, int r) {
	t[root].l = l;
	t[root].r = r;
	t[root].max = INT_MIN;
	t[root].min = INT_MAX;
	if (l != r) {
		build(root * 2 + 1, l, (l + r) / 2);
		build(root * 2 + 2, (l + r) / 2 + 1, r);
	}
}

void insert (int root, int i, int v) {
	if (t[root].l == t[root].r) {
		t[root].min = v;
		t[root].max = v;
		return;
	}
	t[root].min = min(t[root].min, v);
	t[root].max = max(t[root].max, v);
	if (i <= (t[root].l + t[root].r) / 2) {
		insert (root * 2 + 1, i, v);
	} else {
		insert (root * 2 + 2, i, v);
	}
}

void search (int root, int l, int r) {
	int mid = (t[root].l + t[root].r) / 2;
	if (mi <= t[root].min && ma >= t[root].max) {
		return;
	}
	if (t[root].l == l && t[root].r == r) {
		mi = min(mi, t[root].min);
		ma = max(ma, t[root].max);
		return;
	}
	if (r <= mid) {
		search (root * 2 + 1, l, r);
	} else if (l >= mid + 1) {
		search (root * 2 + 2, l, r);
	} else {
		search (root * 2 + 1, l, mid);
		search (root * 2 + 2, mid + 1, r);
	}
	return;
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	build(0, 1, n);
	int tmp;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &tmp);
		insert(0, i, tmp);
	}
	for (int i = 1; i <= q; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		mi = INT_MAX;
		ma = INT_MIN;
		search(0, a, b);
		printf("%d\n", ma - mi);
	}
	return 0;
}

Posted in Segment Tree

POJ 2352 Stars

2017/1/23
Problem: http://poj.org/problem?id=2352
Solution: Obvious segment tree.
Another possible solution: BIT
https://github.com/Prionantha/OJ/blob/master/POJ%202352%20-%20BIT.cpp


#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 122005
using namespace std;

long long tree[MAXN] = {0};
long long level[MAXN] = {0};

int n;

struct star {
	int x, y;
};

star s[MAXN];

long long query(int node, int l, int r, int ql, int qr) {
	int sum = 0;
	int mid = (l + r) / 2;
	if (l >= ql && r <= qr) {
		sum = tree[node];
	} else {
		if (ql < mid) {
            sum += query(node * 2, l, mid, ql, qr);
		}
		if (qr > mid) {
            sum += query(node * 2 + 1, mid, r, ql, qr);
		}
	}
	return sum;
}

void add(int node, int l, int r, int x) {
	if (l + 1 == r) {
		tree[node]++;
	} else {
		int mid = (l + r) / 2;
		if (x < mid) {
			add(node * 2, l, mid, x);
		} else {
			add(node * 2 + 1, mid, r, x);
		}
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

int main() {
	scanf("%d", &n);
	int maxn = 0;
	for (int i = 1; i <= n; i ++) {
        scanf("%d%d",&s[i].x, &s[i].y);
		s[i].x++;
        if (s[i].x > maxn) {
            maxn = s[i].x;
        }
	}
	for (int i = 1; i <= n; i ++) {
        int tmp = query(1, 1, maxn + 1, 1, s[i].x + 1);
		level[tmp]++;
		add(1, 1, maxn + 1, s[i].x);
	}
	for(int i = 0; i < n; i ++) {
        printf("%d\n", level[i]);
	}
	return 0;
}