fork(2) download
copy 
  1. #include <iostream>
  2. #include<cstdio>
  3.  
  4. using namespace std;
  5.  
  6. struct node{
  7.     long best,sum,lft,ryt;
  8.     void init(long a){
  9.         best = a;
  10.         sum = a;
  11.         lft = a;
  12.         ryt = a;
  13.     }
  14.     void merge(node a,node b){
  15.         lft = max(a.lft,a.sum+b.lft);
  16.         ryt = max(b.ryt,b.sum+a.ryt);
  17.         sum = a.sum + b.sum;
  18.         best = max( max(a.best,b.best), a.ryt+b.lft);
  19.     }
  20. } segtree[200005];
  21.  
  22. int sn,n,arr[50005];
  23.  
  24.  
  25. node query(int t,int i,int j,int ri,int rj){
  26.     if(ri==i && rj==j){
  27.         return segtree[t];
  28.     }
  29.     int l = 2*t,mid = (i+j)/2;
  30.     if(rj<=mid)
  31.         return query(l,i,mid,ri,rj);
  32.     if(ri>mid)
  33.         return query(l+1,mid+1,j,ri,rj);
  34.     node a,b,temp;
  35.     a = query(l,i,mid,ri,mid);
  36.     b = query(l+1,mid+1,j,mid+1,rj);
  37.     temp.merge(a,b);
  38.     return temp;
  39. }
  40.  
  41. node build(int t,int i,int j){
  42.     if(i == j){
  43.         segtree[t].init(arr[i]);
  44.         return segtree[t];
  45.     }
  46.     node a,b;
  47.     int l=2*t,mid = (i+j)/2;
  48.     a = build(l,i,mid);
  49.     b = build(l+1,mid+1,j);
  50.     segtree[t].merge(a,b);
  51.     return segtree[t];
  52. }
  53.  
  54.  
  55. int main()
  56. {
  57.     int q,a,b;
  58.     node temp;
  59.    scanf("%d",&n);
  60.    for(int i=1;i<=n;i++)
  61.         scanf("%d",&arr[i]);
  62.    build(1,1,n);
  63.    scanf("%d",&q);
  64.    while(q--){
  65.        scanf("%d%d",&a,&b);
  66.        temp = query(1,1,n,a,b);
  67.        printf("%ld\n",temp.best);
  68.    }
  69.    return 0;
  70. }
  71.  
Success #stdin #stdout 0s 6664KB
comments (?)
stdin
copy 
10
-200 3 4 -200 6 2 4 -200 5 6
1
1 10
stdout
copy 
12
https://ideone.com/OF5TZL
segment tree gss1
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!