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;
}


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s