QMAX - Giá trị lớn nhất
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include "stdio.h"
#include "math.h"
int f[16][50050], b[50050], po[16], n;
int main() {
int i, u, v, val, m, k;
scanf("%d%d",&n,&m);
for(i=0;i<m;++i) {
scanf("%d%d%d",&u,&v,&val);
b[u] += val;
b[v+1] -= val;
}
for(i=1;i<=n;++i) f[0][i]=b[i]+f[0][i-1];
for(k=1,po[0]=1;k<16;++k) {
po[k]=2*po[k-1];
for(i=1;i<=n;++i) {
f[k][i]=f[k-1][i];
if(i+po[k-1]<=n && f[k][i]<f[k-1][i+po[k-1]]) f[k][i]=f[k-1][i+po[k-1]];
}
}
scanf("%d",&m);
for(i=1;i<=m;++i) {
scanf("%d%d",&u,&v);
k = log(v-u+1)/log(2);
val = f[k][u];
if(val<f[k][v-po[k]+1]) val=f[k][v-po[k]+1];
printf("%d\n", val);
}
return 0;
}