Can you answer these queries I

Can you answer these queries I

题目翻译
你得到一个序列 A[1], A[2], …, A[N] 。 ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 )。
查询定义如下：
查询(x,y) = Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }。
给定 M 个查询，您的程序必须输出这些查询的结果。
求最大子序列；

题目分析
只要求最大序列而不要求修改使用猫树模板

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int M = 1e5 + 5;
int m, n, len, a[M];
int lg[M << 2], pos[M], p[21][M], s[21][M];
#define max(a,b) ((a) > (b) ? (a) : (b))
void build(int u,int l,int r,int dep)
{
    if (l == r){
    pos[l] = u;return;}int mid = (l + r) >> 1;int prep = a[mid];int sm = a[mid];p[dep][mid] = a[mid];s[dep][mid] = a[mid];sm = max(sm, 0);for (int i = mid - 1; i >= l; i--){
    prep += a[i], sm += a[i];s[dep][i] = max(s[dep][i + 1], prep);p[dep][i] = max(p[dep][i + 1], sm);sm = max(sm, 0);}p[dep][mid + 1] = a[mid + 1];s[dep][mid + 1] = a[mid + 1];prep = sm = a[mid + 1];sm = max(sm, 0);for (int i = mid + 2; i <= r; i++){
    prep += a[i], sm += a[i];s[dep][i] = max(s[dep][i - 1], prep);p[dep][i] = max(p[dep][i - 1], sm);sm = max(sm, 0);}build(u << 1, l, mid, dep + 1);build(u << 1 | 1, mid + 1, r, dep + 1);return;
}
int query(int l, int r)
{
    if (l == r)return a[l];int d = lg[pos[l]] - lg[pos[l] ^ pos[r]];return max(max(p[d][l], p[d][r]), s[d][l] + s[d][r]);
}
int main() 
{
    cin >> n;for (len = 2; len < n; len <<= 1);for (int i = 1; i <= n; i++) cin>>a[i];for (int l = len * 2, i = 2; i <= l; ++i) lg[i] = lg[i >> 1] + 1;build(1, 1, len, 1);cin >> m;for (int l, r; m; m--){
    cin >> l >> r;cout<<query(l, r)<<endl;}return 0;