QMAX - Giá trị lớn nhất

Problem

https://vn.spoj.com/problems/QMAX

https://oj.vnoi.info/problem/QMAX

Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.

Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị.

Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]

Giới hạn

n, m, q <= 50,000
k > 0
Giá trị của một phần tử luôn không vượt quá 2^31 - 1

Input

Dòng 1: n, m
m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi
Dòng thứ m+2: p
p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi

Output

Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi.

Example

Input
6 2
1 3 2
4 6 3
1
3 4

Output
3

Tutorial

Bài này có 2 bài toán con cần giải quyết. Thứ nhất là xử lý cái vụ cộng mấy số lên k lần trên mỗi đoạn truy vấn. Thứ hai là xử lý các truy vấn max. Cái thứ 2 thì đơn giản rồi nếu ta đã có được mảng kết quả của các truy vấn đầu tiên, bằng cách sử dụng segment tree hoặc RMQ để tìm max trên từng đoạn.

Vậy còn bài toán thứ nhất. Ta sử dụng trick như sau: Với đoạn [l,r] được tăng lên k đơn vị, ta tăng a[l] lên k, sau đó thằng a[r+1] ta giảm đi k. Khi đó sau m truy vấn tăng, ta duyệt mảng rồi cập nhật a[i] += a[i-1], khi đó những mỗi giá trị trong đoạn [l,r] sẽ được cộng đúng như các truy vấn. Do đó ta chỉ cần O(m) cho các truy vấn cộng.

Submission

QMAX.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef unsigned long long ull;

#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ep emplace_back
#define EL printf("\n")
#define sz(A) (int) A.size()
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FOD(i,r,l) for (int i=r;i>=l;i--)
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


const int N = 50005;
int n, q, a[N], t[N<<2];

void build(int k, int l, int r) {
	if (l == r) {
		t[k] = a[l]; return;
	}
	int m = (l+r)>>1;
	build(k<<1, l, m);
	build(k*2+1, m+1, r);
	t[k] = max(t[k<<1], t[k*2+1]);
}

int findMax(int k, int l, int r, int L, int R) {
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return t[k];
	int m = (l+r)>>1;
	return max(findMax(k<<1, l, m, L, R), findMax(k*2+1, m+1, r, L, R));
}

int main() {
//	freopen("INP.TXT", "r", stdin);
//  freopen("OUT.TXT", "w", stdout);

	cin >> n >> q;
	while (q--) {
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		a[l] += k;
		a[r+1] -= k;
	}
	FOR(i,2,n) a[i] += a[i-1];

	build(1,1,n);
	cin >> q;
	while (q--) {
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", findMax(1,1,n,l,r));
	}

	return 0;
}

Tutorial SPOJ