线段树节点信息合并-白红宇

线段树节点信息合并

阅读量：7078 次

发布时间：2019-06-28

本文共 2492 字，大约阅读时间需要 8 分钟。

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:

Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.

Given M queries, your program must output the results of these queries.

Input

The first line of the input file contains the integer N.

In the second line, N numbers follow.

The third line contains the integer M.

M lines follow, where line i contains 2 numbers xi and yi.

Output

Your program should output the results of the M queries, one query per line.

Example

Input:3 -1 2 311 2Output:2 动态查询区间最大子段和。 维护区间和sum，最大前缀和pre，最大后缀和suf，并利用前面三个值来维护最大子段和mx

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include 
           
            #include 
            
             #include
             
              #include
              #include
               
                using namespace std;typedef long long LL;const int maxn = 5e4+5;const int mod = 77200211+233;typedef pair
                
                  pii;#define X first#define Y second#define pb push_back//#define mp make_pair#define ms(a,b) memset(a,b,sizeof(a))const int inf = 0x3f3f3f3f;#define lson l,m,2*rt#define rson m+1,r,2*rt+1typedef long long ll;struct node{ int l,r; int sum,mx,pre,suf; int mid(){ return (l+r)>>1; }}tree[maxn<<2];void push_up(int rt){ tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum; tree[rt].mx = max(tree[rt<<1].suf+tree[rt<<1|1].pre,max(tree[rt<<1].mx,tree[rt<<1|1].mx)); tree[rt].suf = max(tree[rt<<1|1].suf, tree[rt<<1|1].sum+tree[rt<<1].suf); tree[rt].pre = max(tree[rt<<1|1].pre+tree[rt<<1].sum, tree[rt<<1].pre);}void build(int l,int r,int rt){ tree[rt].l=l,tree[rt].r=r; if(l==r){ scanf("%d",&tree[rt].sum); tree[rt].mx=tree[rt].pre=tree[rt].suf=tree[rt].sum; return; } int m = tree[rt].mid(); build(l,m,rt<<1); build(m+1,r,rt<<1|1); push_up(rt);}int qpre(int l,int r,int rt){ if(l<=tree[rt].l && r>= tree[rt].r){ return tree[rt].pre; } int m = tree[rt].mid(); if(r<=m) return qpre(l,r,rt<<1); else return max(tree[rt<<1].pre, tree[rt<<1].sum+qpre(l,r,rt<<1|1));}int qsuf(int l,int r,int rt){ if(l<=tree[rt].l && r>= tree[rt].r){ return tree[rt].suf; } int m = tree[rt].mid(); if(l>m) return qsuf(l,r,rt<<1|1); else return max(tree[rt<<1|1].suf, tree[rt<<1|1].sum+qsuf(l,r,rt<<1));}int qmx(int l,int r,int rt){ if(l<=tree[rt].l && tree[rt].r<=r){ return tree[rt].mx; } int m = tree[rt].mid(); int ans = -inf; if(l<=m) ans = max(ans,qmx(l,r,rt<<1)); if(r>m) ans=max(ans,qmx(l,r,rt<<1|1)); if(l<=m&&m