Đề bài:
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 <= 50000
k > 0
Giá trị của một phần tử luôn không vượt quá 231-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
Gợi ý: Sử dụng interval tree
https://nguyenvanquan7826.wordpress.com/2013/11/09/spoj-qmax/
code:
#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;
// trong do a la mang luu thong tin
// T la cay interval tree
// n la so phan tu
// m la so phep bien doi
// q la so cau hoi
// u la gia tri phan tu dau
// v la gia tri phan tu cuoi
// k gia tri trong khoang u v se duoc tang k don vi
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);
cout<<"Nhap hai gia tri n , m"<<endl;
scanf("%d %d", &n, &m);//cin >> n >> m;
a = new int[n+2];
T = new int[4*n]; // interval tree su dung mang co so phan tu toi da la 4*n -5
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;
}
