QMAX2 - Giá trị lớn nhất ver2
Tác giả: khuc_tuan
Ngôn ngữ: Java
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();
}
}