Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=50000;
var i,x,y,n,val,m,p,re:longint;
    a,mx:array[1..maxn shl 2] of longint;

function min(a,b:longint):longint;
begin
     if a<b then min:=a else min:=b;
end;

function max(a,b:longint):longint;
begin
     if a>b then max:=a else max:=b;
end;

procedure add(node,l,r,x,y:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then
     begin
          a[node]:=a[node]+val;
          mx[node]:=mx[node]+val;
     end
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then add(node shl 1,l,mid,x,min(y,mid));
          if mid<y then add(node shl 1+1,mid+1,r,max(x,mid+1),y);
          mx[node]:=max(mx[node shl 1],mx[node shl 1+1])+a[node];
     end;
end;

procedure findmax(node,l,r,x,y:longint;var t:longint);
var mid,u,v:longint;
begin
     if (l=x) and (r=y) then t:=mx[node]
     else
     begin
          mid:=(l+r) shr 1; u:=-maxlongint; v:=u;
          if x<=mid then findmax(node shl 1,l,mid,x,min(y,mid),u);
          if mid<y then findmax(node shl 1+1,mid+1,r,max(x,mid+1),y,v);
          t:=max(u,v)+a[node];
     end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     readln(n,m);
     for i:=1 to m do
     begin
          readln(x,y,val);
          add(1,1,n,x,y);
     end;
     readln(p);
     for i:=1 to p do
     begin
          readln(x,y);
          findmax(1,1,n,x,y,re);
          writeln(re);
     end;
     close(input); close(output);
end.

Code mẫu của happyboy99x

/* ALGO: Segment Tree */
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;

#define N 300000+5
int seg[N], add[N];

void update(int k, int l, int r, int u, int v, int value) {
    if(l > r || v < l || u > r) return;
    if(u <= l && r <= v) {
        seg[k] += value; add[k] += value;
        return;
    }
    update(k*2, l, (l+r)/2, u, v, value);
    update(k*2+1, (l+r)/2+1, r, u, v, value);
    seg[k] = max(seg[k*2], seg[k*2+1]) + add[k];
}

int get(int k, int l, int r, int u, int v) {
    if(l > r || v < l || u > r) return INT_MIN;
    if(u <= l && r <= v) return seg[k]; 
    return max(get(k*2, l, (l+r)/2, u, v), get(k*2+1, (l+r)/2+1, r, u, v)) + add[k];
}

int main() {
    int n, m; scanf("%d%d",&n,&m);
    for(int i = 0; i < m; ++i) {
        int u, v, k; scanf("%d%d%d",&u,&v,&k);
        update(1, 1, n, u, v, k);
    }
    int p; scanf("%d",&p);
    for(int i = 0; i < p; ++i) {
        int u, v; scanf("%d%d",&u,&v);
        printf("%d\n", get(1, 1, n, u, v));
    }
    return 0;
}

Code mẫu của ladpro98

#include <cstdio>
#include <iostream>

const int N = 100005;

using std::string;
using std::max;

// FAST I/O

static struct IO {
    char tmp[1 << 10];

    // fast input routines
    char cur;

//#define nextChar() (cur = getc_unlocked(stdin))
//#define peekChar() (cur)
    inline char nextChar() { return cur = getc_unlocked(stdin); }
    inline char peekChar() { return cur; }

    inline operator bool() { return peekChar(); }
    inline static bool isBlank(char c) { return (c < '-' && c); }
    inline bool skipBlanks() { while (isBlank(nextChar())); return peekChar() != 0; }

    inline IO& operator >> (char & c) { c = nextChar(); return *this; }

    inline IO& operator >> (char * buf) {
        if (skipBlanks()) {
            if (peekChar()) {
                *(buf++) = peekChar();
                while (!isBlank(nextChar())) *(buf++) = peekChar();
            } *(buf++) = 0; } return *this; }

    inline IO& operator >> (string & s) {
        if (skipBlanks()) { s.clear(); s += peekChar();
            while (!isBlank(nextChar())) s += peekChar(); }
        return *this; }

    inline IO& operator >> (double & d) { if ((*this) >> tmp) sscanf(tmp, "%lf", &d); return *this; }

#define defineInFor(intType) \
    inline IO& operator >>(intType & n) { \
        if (skipBlanks()) { \
            int sign = +1; \
            if (peekChar() == '-') { \
                sign = -1; \
                n = nextChar() - '0'; \
            } else \
                n = peekChar() - '0'; \
            while (!isBlank(nextChar())) { \
                n += n + (n << 3) + peekChar() - 48; \
            } \
            n *= sign; \
        } \
        return *this; \
    }

defineInFor(int)
defineInFor(unsigned int)
defineInFor(long long)

    // fast output routines

//#define putChar(c) putc_unlocked((c), stdout)
    inline void putChar(char c) { putc_unlocked(c, stdout); }
    inline IO& operator << (char c) { putChar(c); return *this; }
    inline IO& operator << (const char * s) { while (*s) putChar(*s++); return *this; }

    inline IO& operator << (const string & s) { for (int i = 0; i < (int)s.size(); ++i) putChar(s[i]); return *this; }

    char * toString(double d) { sprintf(tmp, "%lf%c", d, '\0'); return tmp; }
    inline IO& operator << (double d) { return (*this) << toString(d); }


#define defineOutFor(intType) \
    inline char * toString(intType n) { \
        char * p = (tmp + 30); \
        if (n) { \
            bool isNeg = 0; \
            if (n < 0) isNeg = 1, n = -n; \
            while (n) \
                *--p = (n % 10) + '0', n /= 10; \
            if (isNeg) *--p = '-'; \
        } else *--p = '0'; \
        return p; \
    } \
    inline IO& operator << (intType n) { return (*this) << toString(n); }

defineOutFor(int)
defineOutFor(long long)

#define endl ('\n')
#define cout __io__
#define cin __io__
} __io__;

// END OF FAST I/O

int node[N]; // zero based

int n, m, q;
int a[N];

void build() {
    for (int i = n - 1; i > 0; --i)
        node[i] = max(node[i << 1], node[i << 1 | 1]);
}

void update(int p, int value) {
    for (node[p += n] = value; p > 1; p >>= 1)
        node[p >> 1] = max(node[p], node[p ^ 1]);
}

int getMax(int l, int r) {
    // [l, r)
    int ans = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans = max(ans, node[l++]);
        if (r & 1) ans = max(ans, node[--r]);
    }
    return ans;
}


int main() {
    cin >> n >> m;
    int u, v, k;
    while (m--) {
        cin >> u >> v >> k;
        a[--u] += k; a[v] -= k;
    }
    for (int i = 1; i < n; ++i) {
        a[i] += a[i - 1];
        node[i + n] = a[i];
    }
    build();
    cin >> q;
    while (q--) {
        cin >> u >> v;
        cout << getMax(--u, v) << '\n';
    }
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const double PI = acos(-1.0);
const int MN = 12-1;
const int oo = 1000111000;

int u, v, k, it[262144], ln[262144], a[50111];

#define CT(x) ((x)<<1)
#define CP(x) (CT(x) + 1)

inline void update(int i, int l, int r) {
    if (v < l || r < u) return ;
    if (u <= l && r <= v) {
        it[i] += k;
        ln[i] += k;
        return ;
    }
    if (r - l <= MN) {
        FOR(x,l,r)
            if (u <= x && x <= v) {
                a[x] += k;
                ln[i] = max(ln[i], a[x] + it[i]);
            }
        return ;
    }
    int mid = (l + r) >> 1;
    update(CT(i), l, mid);
    update(CP(i), mid+1, r);

    ln[i] = max(ln[CT(i)], ln[CP(i)]) + it[i];
}

inline int get(int i, int l, int r) {
    if (v < l || r < u) return -oo;
    if (u <= l && r <= v) return ln[i];

    if (r - l <= MN) {
        int res = -oo;
        FOR(x,l,r)
            if (u <= x && x <= v) {
                res = max(res, a[x]);
            }
        return res + it[i];
    }

    int mid = (l + r) >> 1;
    return max(get(CT(i), l, mid), get(CP(i), mid+1, r)) + it[i];
}

char output[30111000];
char *curOutPos, *s;

void write(int res) {
    if (!res) {
        (*curOutPos++) = '0';
        (*curOutPos++) = '\n';
        return ;
    }
    if (res < 0) {
        (*curOutPos++) = '-';
        res = -res;
    }
    s = curOutPos;
    while (res) {
        (*curOutPos++) = res%10 + '0';
        res /= 10;
    }

    reverse(s, curOutPos);
    (*curOutPos++) = '\n';
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    curOutPos = output;
    int n, m, q;
    GN(n); GN(m);
    while (m--) {
        GN(u); GN(v); GN(k);
        update(1,1,n);
    }
    GN(q);
    while (q--) {
        GN(u); GN(v);
        write(get(1,1,n));
    }
    fwrite(output, 1, curOutPos - output, stdout);
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int f[200000],a[50001],KQ;


int max(int x,int y)
{
    if(x>y)
    return x;
    return y;
}

void thietlap(int x,int y,int d)
{
     if(x==y)
         f[d]=a[x];
     else 
     {
          thietlap(x,(x+y)/2,2*d);
          thietlap((x+y)/2+1,y,2*d+1);
          f[d]=max(f[2*d],f[2*d+1]);
     }
}

void tinh(int dau,int cuoi,int x,int y,int d)
{
     if(dau>y||cuoi<x);
     else if(dau<=x&&cuoi>=y)
         KQ=max(KQ,f[d]);
     else
     {
         tinh(dau,cuoi,x,(x+y)/2,2*d);
         tinh(dau,cuoi,(x+y)/2+1,y,2*d+1);
     }
}

main()
{
      int n,m,p,x,y,u;
      scanf("%d %d",&n,&m);
      a[0]=0;
      for(int i=1;i<=m;i++)
      {     
           scanf("%d %d %d",&x,&y,&u);
           a[x]=a[x]+u;
           a[y+1]=a[y+1]-u;
      }
      for(int i=2;i<=n;i++)
           a[i]=a[i-1]+a[i];
      thietlap(1,n,1);
      scanf("%d",&p);
      for(int i=1;i<=p;i++)
      {
           scanf("%d %d",&x,&y);
           KQ=0;
           tinh(x,y,1,n,1);
           printf("%d\n",KQ);
      }
     // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program QMAX1_3;
Uses math;
Const
  input  = '';
  output = '';
  maxn = 50000;
Type
  rec = record
    ins,und: integer;
  end;
Var
  fi,fo: text;
  n,m,p: integer;
  u,v,k: integer;
  a: array[1..8 * maxn] of rec;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure update(i,low,high: integer);
Var
  mid: integer;
Begin
  If (v < low) or (high < u) then exit;
  If (u <= low) and (high <= v) then
    Begin
      inc(a[i].ins,k);
      exit;
    End;

  mid:= (low + high) div 2;
  update(2 * i,low,mid);
  update(2 * i + 1,mid + 1,high);
  a[i].und:= max(a[2 * i].ins + a[2 * i].und,a[2 * i + 1].ins + a[2 * i + 1].und);
End;

Function calc(i,low,high: integer): integer;
Var
  mid: integer;
Begin
  If (v < low) or (high < u) then exit(0);
  If (u <= low) and (high <= v) then exit(a[i].ins + a[i].und);

  mid:= (low + high) div 2;
  calc:= max(calc(2 * i,low,mid),calc(2 * i + 1,mid + 1,high)) + a[i].ins;
End;

Procedure swap(var x,y: integer);
Var
  t: integer;
Begin
  t:= x;
  x:= y;
  y:= t;
End;

Procedure solve;
Var
  i: integer;
Begin
  Fillchar(a, sizeof(a), 0);

  Readln(fi, n, m);
  For i:= 1 to m do
    Begin
      Readln(fi, u, v, k);
      If u > v then swap(u,v);
      update(1,1,n);
    End;

  Readln(fi, p);
  For i:= 1 to p do
    Begin
      Readln(fi, u, v);
      If u > v then swap(u,v);
      Writeln(fo, calc(1,1,n));
    End;
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;
  solve;
  closefile;
End.

Code mẫu của skyvn97

#include<cstdio>
#define MAX   50505
#define INF   2e9
int t[4*MAX];
int c[4*MAX];
int m,n,p;
void init(void) {
    scanf("%d",&n); 
    int i;
    for (i=1;i<=4*n;i=i+1) {
        t[i]=0;
        c[i]=0;
    }   
}
int max(int x,int y) {
    if (x>y) return (x); else return (y);
}
void update(int i,int l,int r,int u,int v,int d) {
    if (r<u) return;
    if (l>v) return;
    if ((u<=l) && (r<=v)) {
        c[i]+=d;
        t[i]+=d;
        return;
    }
    c[2*i]+=c[i];
    c[2*i+1]+=c[i];
    t[2*i]+=c[i];
    t[2*i+1]+=c[i];
    c[i]=0;
    int m=(l+r)/2;
    update(2*i,l,m,u,v,d);
    update(2*i+1,m+1,r,u,v,d);
    t[i]=max(t[2*i],t[2*i+1]);
}
int get(int i,int l,int r,int u,int v,int add) {
    if (r<u) return (-INF);
    if (l>v) return (-INF);
    if ((u<=l) && (r<=v)) return (t[i]+add);
    add+=c[i];
    int m=(l+r)/2;
    int left=get(2*i,l,m,u,v,add);
    int right=get(2*i+1,m+1,r,u,v,add);
    return (max(left,right));
}
void process(void) {
    int u,v,k;
    int i;
    scanf("%d",&m);
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&k);
        update(1,1,n,u,v,k);        
    }
    scanf("%d",&p);
    for (i=1;i<=p;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        printf("%d\n",get(1,1,n,u,v,0));
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include "stdio.h"
#include "math.h"

int f[16][50050], b[50050], po[16], n;

int main() {
    int i, u, v, val, m, k;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i) {
        scanf("%d%d%d",&u,&v,&val);
        b[u] += val;
        b[v+1] -= val;
    }
    for(i=1;i<=n;++i) f[0][i]=b[i]+f[0][i-1];
    for(k=1,po[0]=1;k<16;++k) {
        po[k]=2*po[k-1];
        for(i=1;i<=n;++i) {
            f[k][i]=f[k-1][i];
            if(i+po[k-1]<=n && f[k][i]<f[k-1][i+po[k-1]]) f[k][i]=f[k-1][i+po[k-1]];
        }
    }
    scanf("%d",&m);
    for(i=1;i<=m;++i) {
        scanf("%d%d",&u,&v);
        k = log(v-u+1)/log(2);
        val = f[k][u];
        if(val<f[k][v-po[k]+1]) val=f[k][v-po[k]+1];
        printf("%d\n", val);
    }
    return 0;
}