Pagini recente » Cod sursa (job #2183369) | Cod sursa (job #724433) | Cod sursa (job #2824644) | Cod sursa (job #1272993) | Cod sursa (job #643312)
Cod sursa(job #643312)
#include<fstream>
#define inf "sequencequery.in"
#define outf "sequencequery.out"
#define NMax 100010
#define Dim 131072
#define INF 0x3f3f3f3f
using namespace std;
fstream f(inf,ios::in), g(outf,ios::out);
int N, M, V[NMax]; int start, end;
long long A[Dim], B[Dim], C[Dim], D[Dim];
long long s, sol;
inline long long max(long long x, long long y) { return ( x>y ? x : y ); }
void build(int n, int left, int right)
{
if( left==right ) {
A[n] = B[n] = C[n] = D[n] = V[left];
return;
}
int m = (left+right)/2;
build(2*n, left, m);
build(2*n+1, m+1, right);
A[n] = max( A[2*n], D[2*n]+A[2*n+1] );
B[n] = max( B[2*n+1], D[2*n+1]+B[2*n] );
C[n] = max( max(C[2*n],C[2*n+1]), B[2*n]+A[2*n+1]);
D[n] = D[2*n]+D[2*n+1];
}
void query(int n, int left, int right) //start, end
{
if( left>=start && right<=end ) {
if( s<0 ) s = 0;
sol = max(sol, max(s+A[n], C[n]));
s = max(s+D[n], B[n]);
return;
}
int m = (left+right)/2;
if( start<=m ) query(2*n, left, m);
if( m<end ) query(2*n+1, m+1, right);
}
int main()
{
f>>N>>M;
for(int i=1; i<=N; i++) f>>V[i];
build(1,1,N);
for(int i=1; i<=M; i++)
{
f>>start>>end;
s = 0; sol = -INF;
query(1,1,N);
g<<sol<<"\n";
}
f.close(); g.close();
return 0;
}