Created
January 19, 2015 12:07
-
-
Save Se7soz/ebd1456340b5da63ebaf to your computer and use it in GitHub Desktop.
Can you answer these queries I
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <cstdio> | |
#include <cmath> | |
#include <queue> | |
#include <cstring> | |
#include <map> | |
#include <climits> | |
#include <set> | |
using namespace std; | |
struct node { | |
int ans, sum, suf, pref; | |
node() {} | |
}; | |
node tree[200000]; | |
int n; | |
node make_node(int v) { | |
node ret; | |
ret.ans = ret.sum = ret.suf = ret.pref = v; | |
return ret; | |
} | |
node combineSegments(node left, node right) { | |
node ret; | |
ret.sum = left.sum+right.sum; | |
ret.pref = max(left.pref, left.sum+right.pref); | |
ret.suf = max(right.suf, right.sum+left.suf); | |
ret.ans = max(max(left.ans, right.ans), left.suf+right.pref); | |
return ret; | |
} | |
void buildTree(int a[], int x, int l, int r) { | |
if(l == r) | |
tree[x] = make_node(a[l]); | |
else { | |
int mid = (l+r)/2; | |
buildTree(a, x*2, l, mid); | |
buildTree(a, x*2+1, mid+1, r); | |
tree[x] = combineSegments(tree[x*2], tree[x*2+1]); | |
} | |
} | |
node queryTree(int x, int a, int b, int i, int j) { | |
int mid = (a+b)/2; | |
if(a >= i && b <= j) return tree[x]; | |
if(j <= mid) return queryTree(x*2, a, mid, i, j); | |
else if(i > mid) return queryTree(x*2+1, mid+1, b, i, j); | |
node left = queryTree(x*2, a, mid, i, mid); | |
node right = queryTree(x*2+1, mid+1, b, mid+1, j); | |
return combineSegments(left, right); | |
} | |
int main() { | |
scanf("%d", &n); | |
int nums[n+1]; | |
for(int i = 1; i <= n; i++) scanf("%d", &nums[i]); | |
buildTree(nums, 1, 1, n); | |
int m, x, y; | |
scanf("%d", &m); | |
for(int i = 0; i < m; i++) { | |
scanf("%d %d", &x, &y); | |
printf("%d\n", queryTree(1, 1, n, x, y).ans); | |
} | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
why do we need to write a separate node for this question??