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.
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,>); 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