Editorial for Giá trị lớn nhất ver2


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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,w: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
          read(w);
          if w=0 then
          begin
               readln(x,y,val);
               add(1,1,n,x,y);
          end
          else
          begin
               readln(x,y);
               findmax(1,1,n,x,y,re);
               writeln(re);
          end;
     end;
     close(input); close(output);
end.

Code mẫu của happyboy99x

#include <iostream>
#include <climits>
#include <cstdio>
using namespace std;

const int N = 50000;
int maxValue[4 * N];
int delta[4 * N];

void update(int k, int l, int r, int x, int y, int d) {
    if (l > r || y < l || r < x)
        return;
    if (x <= l && r <= y) {
        maxValue[k] += d;
        delta[k] += d;
    } else {
        update(2 * k + 1, l, (l + r) / 2, x, y, d);
        update(2 * k + 2, (l + r) / 2 + 1, r, x, y, d);
        maxValue[k] = max(maxValue[2 * k + 1], maxValue[2 * k + 2]) + delta[k];
    }
}

int get(int k, int l, int r, int x, int y) {
    if (l > r || y < l || r < x)
        return INT_MIN;
    if (x <= l && r <= y)
        return maxValue[k];
    return max(get(2 * k + 1, l, (l + r) / 2, x, y), get(2 * k + 2, (l + r) / 2 + 1, r, x, y)) + delta[k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int type, x, y;
        cin >> type >> x >> y;
        --x;
        --y;
        if (type == 0) {
            int delta;
            cin >> delta;
            update(0, 0, n - 1, x, y, delta);
        } else {
            printf("%d\n", get(0, 0, n - 1, x, y));
        }
    }
    return 0;
}

Code mẫu của ladpro98

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String args[]) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver object = new Solver();
        object.solve(in, out);
        out.close();
    }

    static class Solver {
        public void solve(InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int a[] = new int[n + 1];
            SegmentTree T = new SegmentTree(a);
            for (int i = 1; i <= m; ++i) {
                int type = in.nextInt();
                int x = in.nextInt();
                int y = in.nextInt();
                if (type == 0) {
                    int value = in.nextInt();
                    T.increase(x, y, value);
                } else {
                    out.println(T.getMaxValue(x, y));
                }
            }
        }
    }

    static class SegmentTree {
        Node root;

        SegmentTree(int a[]) {
            root = build(a, 1, a.length - 1);
        }

        void increase(int i, int j, int value) {
            root.increase(i, j, value);
        }

        int getMaxValue(int i, int j) {
            return root.getMaxValue(i, j);
        }

        class Node {
            int l, r;
            int lazy;
            int maxValue;
            Node left, right;

            Node(int l, int r) {
                this.l = l;
                this.r = r;
                this.lazy = 0;
                this.maxValue = 0;
                this.left = null;
                this.right = null;
            }

            void gather() {
                maxValue = Math.max(left.maxValue, right.maxValue);
            }

            void pushDown() {
                if (lazy != 0) {
                    maxValue += lazy;
                    if (l != r) {
                        left.lazy += lazy;
                        right.lazy += lazy;
                    }
                    lazy = 0;
                }
            }

            int getMaxValue(int i, int j) {
                pushDown();
                if (r < i || j < l) return 0;
                if (i <= l && r <= j) return maxValue;
                return Math.max(left.getMaxValue(i, j), right.getMaxValue(i, j));
            }

            void increase(int i, int j, int value) {
                pushDown();
                if (r < i || j < l) return;
                if (i <= l && r <= j) {
                    lazy += value;
                    pushDown();
                    return;
                }
                left.increase(i, j, value);
                right.increase(i, j, value);
                gather();
            }
        }

        Node build(int a[], int l, int r) {
            Node cur = new Node(l, r);
            if (l == r) {
                cur.maxValue = a[l];
                return cur;
            }
            int mid = l + r >> 1;
            cur.left = build(a, l, mid);
            cur.right = build(a, mid + 1, r);
            cur.gather();
            return cur;
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

Code mẫu của RR

#include <bits/stdc++.h>
#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 DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR(A,n)  { cout << #A << " = "; FOR(_,1,n) cout << A[_] << ' '; cout << endl; }
#define PR0(A,n) { cout << #A << " = "; REP(_,n) cout << A[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
#define __builtin_popcount __builtin_popcountll
#define SZ(x) ((int) (x).size())
using namespace std;

double safe_sqrt(double x) {
    return sqrt(max((double)0.0,x));
}
int GI(ll& x) {
    return scanf("%lld", &x);
}

const int MAXN = 50111;
struct Node {
    int lazy; // giá trị T trong phân tích trên
    int val; // giá trị lớn nhất
} nodes[MAXN * 4];

void down(int id) {
    int t = nodes[id].lazy;
    nodes[id*2].lazy += t;
    nodes[id*2].val += t;
    nodes[id*2+1].lazy += t;
    nodes[id*2+1].val += t;
    nodes[id].lazy = 0;
}

void update(int id, int l, int r, int u, int v, int val) {
    if (v < l || r < u) {
        return ;
    }
    if (u <= l && r <= v) {
        nodes[id].val += val;
        nodes[id].lazy += val;
        return ;
    }
    int mid = (l + r) / 2;

    down(id);
    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);

    nodes[id].val = max(nodes[id*2].val, nodes[id*2+1].val);
}

int get(int id, int l, int r, int u, int v) {
    if (v < l || r < u) {
        return -2000111000;
    }
    if (u <= l && r <= v) {
        return nodes[id].val;
    }
    int mid = (l + r) / 2;
    down(id);

    return max(get(id*2, l, mid, u, v),
        get(id*2+1, mid+1, r, u, v));
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    while (q--) {
        int typ; cin >> typ;
        if (typ == 0) {
            int l, r, val; cin >> l >> r >> val;
            update(1, 1, n, l, r, val);
        }
        else {
            int l, r; cin >> l >> r;
            printf("%d\n", get(1, 1, n, l, r));
        }
    }
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, 0, -1, +1};
const int dc[] = {-1, +1, 0, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = ld(1e-12);
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 50005

using namespace std;

int n, m, dt[maxn * 6], f[maxn * 6];

void updateMax(int id){
    f[id] = max(dt[2*id] + f[2*id], dt[2*id + 1] + f[2*id + 1]);
}

void updateValue(int id){
     dt[2*id] += dt[id];
     dt[2*id + 1] += dt[id];
     dt[id] = 0;
}

void update(int id,int l,int r,int u,int v,int add){
     int mid;
     if(u > r || v < l) return;
     if(u <= l && v >= r){
          dt[id] += add;
          return;
     }

     updateValue(id);   
     mid = (l + r) >> 1;
     update(2*id, l, mid, u, v, add);
     update(2*id + 1, mid + 1, r, u, v, add);
     updateMax(id);
}

int getmax(int id,int l,int r,int u,int v){
     int mid, t1, t2;
     if(u > r || v < l) return -inf;

     updateValue(id);
     if(u <= l && v >= r){
          updateMax(id); 
          return f[id];
     }

     mid = (l + r) >> 1;
     t1 = getmax(2*id , l, mid, u, v);
     t2 = getmax(2*id + 1, mid + 1, r, u, v);
     updateMax(id);
     return max(t1, t2);     
}

int main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    scanf("%d %d",&n,&m);
    memset(dt,0,sizeof(dt));
    memset(f,0,sizeof(f));
    int hoi, x, y, gt;
    for(int i = 1;i<=m;i++){
         scanf("%d",&hoi);
         if(hoi){
              scanf("%d %d",&x,&y);
              printf("%d\n",getmax(1,1,n,x,y));
         }
         else{
              scanf("%d %d %d",&x,&y,&gt);
              update(1,1,n,x,y,gt);
         }
    }
  //  getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program QMAX2_2;
Uses math;
Const
  input  = '';
  output = '';
  maxn = 50000;
Type
  rec = record
    ins,und: integer;
  end;
Var
  fi,fo: text;
  n,m,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,q: integer;
Begin
  Fillchar(a, sizeof(a), 0);

  Readln(fi, n, m);
  For i:= 1 to m do
    begin
      Read(fi, q, u, v);
      If u > v then swap(u,v);
      If q = 0 then
        Begin
          Readln(fi, k);
          update(1,1,n);
        End
      else 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   300005
#define INF   2e9
int n,m;
int t[MAX];
int c[MAX];
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 (l>v) return;
    if (r<u) return;
    if (r<l) return;
    if ((u<=l) && (r<=v)) {
        t[i]+=d;
        c[i]+=d;
        return;
    }   
    update(2*i,l,(l+r)/2,u,v,d);
    update(2*i+1,(l+r)/2+1,r,u,v,d);
    t[i]=max(t[2*i],t[2*i+1])+c[i]; 
}
int get(int i,int l,int r,int u,int v) {
    if (l>v) return (-INF);
    if (r<u) return (-INF);
    if (r<l) return (-INF);
    if ((u<=l) && (r<=v)) return (t[i]);
    return (max(get(2*i,l,(l+r)/2,u,v),get(2*i+1,(l+r)/2+1,r,u,v)))+c[i];
}
void process(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i,t,u,v,k;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&t); 
        scanf("%d",&u);
        scanf("%d",&v);
        if (t==0) {
            scanf("%d",&k);
            update(1,1,n,u,v,k);
        }
        else printf("%d\n",get(1,1,n,u,v));
    }
}
int main(void) {
    process();
    return 0;
}

Code mẫu của khuc_tuan

import java.util.*;
import java.io.*;

public class Main {
    int n,m,p,result,sum;
    int[] total,max;

    void update( int n,int l,int r,int x,int y,int v){
        if(x<=l && r<=y){
            total[n]+=v;
            max[n]+=v;
            return;
        }
        int m=(l+r)/2;
        if(x<=m) update(2*n,l,m,x,y,v);
        if(m<y) update(2*n+1,m+1,r,x,y,v);
        max[n]=total[n]+Math.max(max[2*n],max[2*n+1]);
    }

    void tinh(int n,int l,int r,int x,int y){
        if(x<=l && r<=y){
            result=Math.max(result,sum+max[n]);
            return;
        }
        int m=(l+r)/2;
        sum+=total[n];
        if(x<=m) tinh(2*n,l,m,x,y);
        if(m<y) tinh(2*n+1,m+1,r,x,y);
        sum-=total[n];
    }

    void nhap() throws Exception{
        int u,v,value,code;
        BufferedReader kb=new BufferedReader(new InputStreamReader(System.in), 65536);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(kb.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        int ran=1;
        while(ran<2*n) ran*=2;
        total=new int[ran+1];
        max=new int[ran+1];
        for(int i=0;i<m;++i){
            st=new StringTokenizer(kb.readLine());
            code=Integer.parseInt(st.nextToken());
            if(code==0){
                u=Integer.parseInt(st.nextToken());
                v=Integer.parseInt(st.nextToken());
                value=Integer.parseInt(st.nextToken());
                update(1,1,n,u,v,value);
            }
            else{
                u=Integer.parseInt(st.nextToken());
                v=Integer.parseInt(st.nextToken());
                result=-1000000000;
                sum=0;
                tinh(1,1,n,u,v);
                out.println(result);
            }
        }
        out.flush();
    }

    void run() throws Exception{
        nhap();
    }

    public static void main(String[] args) throws Exception{
        new Main().run();
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.