Skip to content

Instantly share code, notes, and snippets.

@Se7soz
Created January 19, 2015 12:07
Show Gist options
  • Save Se7soz/ebd1456340b5da63ebaf to your computer and use it in GitHub Desktop.
Save Se7soz/ebd1456340b5da63ebaf to your computer and use it in GitHub Desktop.
Can you answer these queries I
#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;
}
@harshag96
Copy link

why do we need to write a separate node for this question??

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment