Interval tree

Đề 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;

}