Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define pb push_back
- #define mp make_pair
- #define pii pair<int,int>
- #define vi vector<int>
- #define all(a) (a).begin(),(a).end()
- #define lol 1000000007
- #define endl '\n'
- #define rep(i,a,b) for(int i=a;i<b;i++)
- #define SIZE 50000
- using namespace std;
- void MOD(ll &x)
- {
- if (x >= lol) x -= lol;
- if (x < 0) x += lol;
- }
- struct segtree
- {
- ll maxsubsum;
- ll sum;
- ll maxprefsum;
- ll maxsufsum;
- };
- //////////////////////////////////////
- ll arr[SIZE+5];
- segtree tree[4*SIZE+5]; //arr and tree are both 1-indexed//
- int n, q; //////////////////////////////////////
- void build(int node, int start, int end)
- {
- if(start==end)
- {
- tree[node].maxsubsum = arr[start];
- tree[node].sum = arr[start];
- tree[node].maxprefsum = arr[start];
- tree[node].maxsufsum = arr[start];
- }
- else
- {
- int mid = (start+end)/2;
- build(2*node, start, mid);
- build(2*node+1, mid+1, end);
- //tree[node].sum=tree[node].maxprefsum=LLONG_MIN;
- //tree[node].maxsufsum=tree[node].maxsubsum=LLONG_MIN;
- tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
- tree[node].maxprefsum = max(tree[2*node].maxprefsum, tree[2*node].sum + tree[2*node+1].maxprefsum);
- tree[node].maxsufsum = max(tree[2*node+1].maxsufsum, tree[2*node+1].sum + tree[2*node].maxsufsum);
- tree[node].maxsubsum = max(tree[2*node].maxsubsum , max(tree[2*node+1].maxsubsum, tree[2*node].maxsufsum + tree[2*node+1].maxprefsum)); //CHANGES ACCORDING TO QUERY
- }
- }
- segtree query(int node, int start, int end, int l, int r)
- {
- segtree result;
- result.sum=result.maxprefsum=LLONG_MIN;
- result.maxsufsum=result.maxsubsum=LLONG_MIN;
- if(r<start || end<l) //range of node is completely outside given range
- {
- return result;
- }
- if(l<=start && end<=r) // range of node is completely inside given range
- {
- return tree[node];
- }
- int mid = (start+end)/2; //range of node is partially inside and partially outside the given range
- if (l > mid)
- return query(2*node+1, mid+1, end, l, r);
- if (r <= mid)
- return query(2*node, start, mid, l, r);
- segtree p1 = query(2*node, start, mid, l, r);
- segtree p2 = query(2*node+1, mid+1, end, l, r);
- result.sum = p1.sum + p2.sum;
- result.maxprefsum = max(p1.maxprefsum, p1.sum + p2.maxprefsum);
- result.maxsufsum = max(p2.maxsufsum, p2.sum + p1.maxsufsum);
- result.maxsubsum = max(p1.maxsubsum , max(p2.maxsubsum, p1.maxsufsum + p2.maxprefsum)); //CHANGES ACCORDING TO QUERY
- return result; //CHANGES ACCORDING TO QUERY
- }
- void solve()
- {
- cin>>n;
- rep(i,1,n+1)
- {
- cin>>arr[i];
- }
- build(1,1,n);
- cin>>q;
- rep(i,1,q+1)
- {
- int x, y;
- cin>>x>>y;
- segtree ans = query(1,1,n,x,y);
- cout<<ans.maxsubsum<<endl;
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t=1;
- // cin>>t;
- while(t--){
- solve();
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment