GSS 시리즈 1 - 8

GSS1 - Can you answer these queries I
Descripition
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 3 1 1 2 Output: 2
Solution
이 문 제 는 주어진 구간 의 최대 부분 과 선분 트 리 로 만 들 면 된다 는 것 이다.그러나 잘 처리 해 야 할 점 은 이 단락 의 최대 부분 과 두 개의 구간 을 뛰 어 넘 을 수 있 기 때문에 우 리 는 왼쪽 에서 최대 치, 오른쪽 에서 최대 치 를 기록 해 야 한다.그리고 pushup 에서 매번 업데이트 해 주세요.코드 를 보 세 요.https://www.cnblogs.com/ztz11/p/9343366.html 우리 가 이 문 제 를 푸 는 데 있어 서 먼저 생각해 야 할 것 은 두 구간 이 어떻게 합병 되 는 지 하 는 것 이다.
합병 후 가장 큰 부분 과 원래 왼쪽 아들 의 것 이 었 거나 원래 오른쪽 아들 의 것 이 었 음 이 분명 하 다.
또 하 나 는 두 아들 을 합병 한 후에 중간 에 새로 생 성 된 것 일 수도 있다.
그래서 각 노드 마다 네 개의 요 소 를 유지 합 니 다.
각각 그 가 관할 하 는 구간 과 그 가 관할 하 는 구간 중 최대 연속 부분 과
왼쪽부터 최대 연속 자 단 과
오른쪽 부터 최대 연속 부분 과
이때 우 리 는 이렇게 이동 할 수 있다.
sum (화) 는 말 할 필요 가 없습니다.
이 층 의 왼쪽 부터 최대 연속 부분 과 = max (왼쪽 아들 의 왼쪽 부터 최대 연속 부분 과 왼쪽 아들 의 합 + 오른쪽 아들 의 왼쪽 부터 최대 연속 부분 과)
이 층 의 왼쪽 부터 최대 연속 부분 과 방법 이 같 습 니 다.
이 층 의 최대 연속 자 단 과 = max (왼쪽 아들 의 최대 연속 자 단 과 오른쪽 아들 의 최대 연속 자 단 과, (왼쪽 아들 이 오른쪽 에서 시작 하 는 최대 연속 필드 와 + 오른쪽 아들 이 왼쪽 에서 시작 하 는 최대 연속 자 단 과 (즉 합병 후 생 성 되 는 중간 최대 자 단))
OK, 퀘 스 트 완성
조회
Code

#include
#include
#include
#include
#include
#define ls (rt<<1)
#define rs (rt<<1|1)
#define INF 0x3f3f3f3f
using namespace std;
struct node{
    int lmax,rmax,max,sum;
//              ，                 （       ）
//    
    node(int x=0) {
        sum=max=lmax=rmax=x;
    }
}tree[1000001];
int ql,qr,n,m;
inline int read(){
    int x=0,w=1;char ch;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();
    return x*w;
}
node pushup(node x,node y) {
    node ans;
    ans.sum=x.sum+y.sum;//   
    ans.max=max(x.rmax+y.lmax,max(x.max,y.max));//    +    ，       
    ans.lmax=max(x.lmax,x.sum+y.lmax);
    ans.rmax=max(y.rmax,y.sum+x.rmax);//  
    return ans;
}
void build(int rt,int l,int r) {
    if(l==r) {
        int x;
        x=read();
        tree[rt]=node(x);
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tree[rt]=pushup(tree[ls],tree[rs]);
}
node query(int rt,int l,int r) {
    if(ql<=l&&r<=qr) return tree[rt];
    //           ，        ，            
    node x(-INF),y(-INF);
    x.sum=y.sum=0;
    int mid=(l+r)>>1;
    if(ql<=mid) x=query(ls,l,mid);
    if(qr>mid) y=query(rs,mid+1,r);
    return pushup(x,y);
}
int main(){
    freopen("gss1.in","r",stdin);
    freopen("gss1.out","w",stdout);
    while(~scanf("%d",&n)) {
        build(1,1,n);
        m=read();
        while(m--) {
            ql=read();qr=read();
            printf("%d
",query(1,1,n).max);
        }
    }
    return 0;
}