[SPOJ] QMAX

Đề bài: http://vn.spoj.com/problems/QMAX/

Bài này chúng ta sử dụng Interval Tree.
Các bạn xem tài liệu này về Interval tree và trong đó cũng có cách giải bài này luôn đó.

/*
 * http://vn.spoj.com/problems/QMAX/
 * nguyenvanquan7826
 */

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

#define INP "QMAX.INP"
#define OUT "QMAX.OUT"

using namespace std;

int ans = 0, *a, *T, n, m, q, u, v, k;

void updateTree(int k, int l, int r){
	int c;
	if (l > r) return;
	if (l == r) { 
		T[k] = a[l]; 
		return;
	}
	c = (l + r) / 2;
	updateTree(k*2, l, c);
	updateTree(k*2 + 1, c + 1, r); 
	T[k] = max(T[k*2], T[k*2+1]);
	return;
}

void findMax(int k, int l, int r, int i, int j){
	int c;
	
	if (l > j || r < i) return;
	if (i <= l && j >= r){
		ans = max(ans, T[k]);
		return;
	}
	c = (l + r) / 2;
	findMax(k*2, l, c, i, j);
	findMax(k*2 + 1, c + 1, r, i, j);
	return;
}

int main(){
	freopen(INP, "r", stdin);
	freopen(OUT, "w", stdout);
	scanf("%d %d", &n, &m);//cin >> n >> m;
	a = new int[n+2];
	T = new int[4*n];
	for (int i = 0; i < n+2; i++)
		a[i] = 0;
	for (int i = 0; i < 4*n; i++)
		T[i] = 0;
	
	for (int i = 1; i <= m; i++){
		scanf("%d %d %d", &u, &v, &k); //cin >> u >> v >> k;
		a[u] += k; 
		a[v+1] -= k;
	}
	
	for (int i = 2; i < n + 1; i++)
		a[i] = a[i] + a[i-1];
	
	updateTree(1, 1, n);
	scanf("%d", &q);//cin >> q;
	ans = 0;
	
	for (int i = 0; i < q; i++){
		scanf("%d %d", &u, &v);//cin >> u >> v;
		ans = 0;
		findMax(1, 1, n, u, v);
		cout << ans << endl;
	}
	
	return 0;
}