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

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

1. Đề bài QMAX2 spoj

Giống bài “Giá trị lớn nhất” ở trên.

Input

– n: số phần tử của dãy (n <= 50000).
– m: số lượng biến đổi và câu hỏi (m <= 100000).
+) biến đổi có dạng: 0 x y value
+) câu hỏi có dạng : 1 x y.

Output

Ghi ra trả lời cho lần lượt từng câu hỏi.

Example

Input:
6 3
0 1 3 3
0 4 6 4
1 1 6

Output:
4

2. code tham khảo QMAX2 spoj

a. Code pascal

uses    math;
const   fi='';
        nmax=50001;
type    data=longint;
var
        f:text;
        add,t:array[0..nmax*5] of data;
        n,m:data;

procedure down(i,trai,phai:data);
begin
        inc(add[trai],add[i]);
        inc(add[phai],add[i]);
        inc(t[trai],add[i]);
        inc(t[phai],add[i]);
        add[i]:=0;
end;


procedure update(i,l,r,u,v,c:data);
var     mid:data;
begin
        if (l=u) and (v=r) then
                begin
                        inc(add[i],c);
                        inc(T[i],c);
                        exit;
                end
        else
        if (r<u) or (v<l) then
                exit;

        mid:=(l+r) div 2;
        down(i,i*2,i*2+1);

        update(i*2,l,mid,u,min(v,mid),c);
        update(i*2+1,mid+1,r,max(mid+1,u),v,c);

        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 (l=u) and (v=r) then
                exit(T[i]);
        if (r<u) or (v<l) then
                exit(0);

        mid:=(l+r) div 2;
        down(i,i*2,i*2+1);
        maxtrai:=timmax(i*2,l,mid,u,min(mid,v));
        maxphai:=timmax(i*2+1,mid+1,r,max(mid+1,u),v);
        exit(max(maxtrai,maxphai));
end;


procedure xuli;
var     i,u,v,c,ch:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,m);

        for i:=0 to n do
                begin
                        t[i]:=0;
                        add[i]:=0;
                end;

        for i:=1 to m do
                begin
                        read(f,ch);
                        if ch=0 then
                                begin
                                        readln(f,u,v,c);
                                        update(1,1,n,u,v,c);
                                end
                        else
                                begin
                                        readln(f,u,v);
                                        writeln(timmax(1,1,n,u,v));
                                end;
                end;
        close(f);
end;


begin
        xuli;
end.

b. Code c++

//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <bitset>
using namespace std;

int n,m,res;
vector<int> T,F;

void Init()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    ios_base::sync_with_stdio(false);
    scanf("%d%d",&n,&m);
    F.resize(8*n + 5);
    T.resize(8*n + 5);
}

void Update(int k, int l, int r, int x, int y, int value)
{
    if(T[k]!=0)
    {
        F[k]+=T[k];
        T[2*k]+=T[k];
        T[2*k+1]+=T[k];
        T[k]=0;
    }
    if(l>y || r<x) return;
    if(x<=l && y>=r)
    {
        F[k]+=value;
        T[2*k]+=value;
        T[2*k+1]+=value;
        T[k]=0;
        return;
    }
    int m=(l+r)/2;
    Update(2*k,l,m,x,y,value);
    Update(2*k+1,m+1,r,x,y,value);
    F[k]=max(F[2*k],F[2*k+1]);
}

void Query(int k, int l, int r, int x, int y)
{
    if(T[k]!=0)
    {
        F[k]+=T[k];
        T[2*k]+=T[k];
        T[2*k+1]+=T[k];
        T[k]=0;
    }
    if(l>y || r<x) return;
    if(x<=l && r<=y)
    {
        res=max(res,F[k]);
        return;
    }
    int m=(l+r)/2;
    Query(2*k,l,m,x,y);
    Query(2*k+1,m+1,r,x,y);
    F[k]=max(F[2*k],F[2*k+1]);
}
void Solve()
{
    while(m--)
    {
        int type;
        scanf("%d",&type);
        if(type==0)
        {
            int x,y,value;
            scanf("%d%d%d",&x,&y,&value);
            Update(1,1,n,x,y,value);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            res=0;
            Query(1,1,n,x,y);
            printf("%dn",res);
        }
    }
}

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