QMAX - Giá trị lớn nhất
Tác giả: skyvn97
Ngôn ngữ: C++
#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;
}