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

Nguồn đề bài: http://vn.spoj.com/problems/QMAX/

1. Đề bài QMAX spoj

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á 2³¹-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

2. Hướng dẫn QMAX spoj

– xử lí phần truy vấn giống như bài MTHCN bạn có thể tham khảo tại đây: https://kienthuc24h.com/2015/01/11/mthcn-spoj-hinh-chu-nhat-ki-la/

– sau đó dùng cây Interval Tree để giải quyết 😀

3. code tham khảo QMAX spoj (pascal, C++)

Pascal

uses    math;
const   fi='';
        nmax=50000;
type    data=longint;

var
        f:text;
        T,A:array[0..nmax*4] of data;
        m,n,q:data;

procedure napdulieu(i,l,r:data);
var     mid:data;
begin
        if l=r then
                begin
                        T[i]:=a[L];
                        exit;
                end;
        mid:=(l+r) div 2;
        napdulieu(i*2,l,mid);
        napdulieu(i*2+1,mid+1,r);
        T[I]:=max(T[i*2],T[i*2+1]);
end;

function timmax(i,l,r,u,v:data):data;
var     mid,maxtrai,maxphai:data;
begin
        if (v<l) or (r<u) then
                exit(0)
        else
                if (u<=l) and (r<=v) then
                        exit(T[i])
                else
                        begin
                                mid:=(l+r) div 2;
                                maxtrai:=timmax(i*2,l,mid,u,v);
                                maxphai:=timmax(i*2+1,mid+1,r,u,v);
                                exit(max(maxtrai,maxphai));

                        end;

end;

procedure xuli;
var     i,j,u,v,k:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,m);
        for i:=0 to n do
                a[i]:=0;

        for i:=1 to m do
                begin
                        readln(f,u,v,k);
                        a[u]:=a[u]+k;
                        a[v+1]:=a[v+1]-k;
                end;
        for i:=1 to n do
                a[i]:=a[i]+a[i-1];

        napdulieu(1,1,n);

        readln(f,q);
        for i:=1 to q do
                begin
                        readln(f,u,v);
                        writeln(timmax(1,1,n,u,v));
                end;
        close(f);
end;



begin
        xuli;
end.

c++

#include <bits/stdc++.h>
using namespace std;

int n,m,q;
vector<int> a;
vector<int> T;
int res;

void Update(int k, int l, int r, int i)
{
	if(l>i || r<i) return;
	if(l==r)
	{
		T[k]=a[i];
		return;
	}
	int m=(l+r)/2;
	Update(2*k,l,m,i);
	Update(2*k+1,m+1,r,i);
	T[k]=max(T[2*k],T[2*k+1]);
}

void Query(int k, int l, int r, int dau, int cuoi)
{
	if(l>cuoi || r<dau) return;
	if(dau<=l && cuoi>=r)
	{
		res=max(res,T[k]);
		return;
	}
	int m=(l+r)/2;
	Query(2*k,l,m,dau,cuoi);
	Query(2*k+1,m+1,r,dau,cuoi);
}

void Init()
{
	cin>>n>>m;
	a.resize(n+2);
	T.resize(4*n);
	for (int i=0;i<m;i++)
	{
		int u,v,k;
		cin>>u>>v>>k;
		a[u]+=k;
		a[v+1]-=k;
	}
	for (int i=1;i<=n;i++)
	{
		a[i]+=a[i-1];
		Update(1,1,n,i);
	}
}

void Solve()
{
	cin>>q;
	for (int i=0;i<q;i++)
	{
		int u,v;
		cin>>u>>v;
		res=0;
		Query(1,1,n,u,v);
		cout<<res<<endl;
	}
}

int main()
{
	Init();
	Solve();
}

QMAX spoj – Giá trị lớn nhất