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

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.

//#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(); }