Cod sursa(job #3376715)

Utilizator Daniel150212daniel munteanu Daniel150212 Data 19 noiembrie 2026 09:11:22
Problema SequenceQuery Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#define int long long
using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
const int MAXN=100005;
const int INF=-100000007;
int v[MAXN];
struct nod{
    int maxint;
    int maxst, maxdr;
    int sumint;
};
nod tree[MAXN*4];
struct AINT{
    AINT() {
        tree[0]={INF, INF, INF, 0};
    }
    nod merge(nod a, nod b){
        int maxx=a.maxdr+b.maxst;
        maxx=max(maxx, a.maxint);
        maxx=max(maxx, b.maxint);
        nod r;
        r.maxint=maxx;
        r.maxst=a.maxst;
        r.sumint=a.sumint+b.sumint;
        if(a.sumint+b.maxst>=a.maxst){
            r.maxst=a.sumint+b.maxst;
        }
        r.maxdr=b.maxdr;
        if(b.sumint+a.maxdr>=b.maxdr){
            r.maxdr=b.sumint+a.maxdr;
        }
        return r;
    }
    void init(int node, int st, int dr){
        if(st==dr){
            nod x;
            x.maxint=v[st];
            x.maxst=v[st];
            x.maxdr=v[st];
            x.sumint=v[st];
            tree[node]=x;
            return;
        }
        int mid=(st+dr)/2;
        init(2*node, st, mid);
        init(2*node+1, mid+1, dr);
        tree[node]=merge(tree[2*node], tree[2*node+1]);
    }
    nod query(int node, int st, int dr, int l, int r){
        if(st>r || dr<l) return tree[0];
        if(st>=l && dr<=r){
            return tree[node];
        }
        int mid=(st+dr)/2;
        return merge(query(2*node, st, mid, l, r), query(2*node+1, mid+1, dr, l, r));
    }
};
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        cin>>v[i];
    }
    AINT aint;
    aint.init(1, 1, n);
    while(q--){
        int l, r;
        cin>>l>>r;
        nod ans=aint.query(1, 1, n, l, r);
        cout<<ans.maxint<<"\n";
    }
}