KGSS - Maximum Sum

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<queue>
#define v   first
#define p   second
#define MAX   100100
using namespace std;
typedef pair<int,int> ii;
const ii INF=ii(-1e9,-1e9);
ii t[3*MAX];
int a[MAX];
int n,m;
ii max(ii x,ii y) {
    if (x>y) return (x); else return (y);
}
void init(void) {
    scanf("%d",&n);
    int i;
    for (i=1;i<=3*n;i=i+1) t[i]=INF;
    for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
}
void build(int i,int l,int r) {
    if (l==r) t[i]=ii(a[l],l);
    else {
        build(2*i,l,(l+r)/2);
        build(2*i+1,(l+r)/2+1,r);
        t[i]=max(t[2*i],t[2*i+1]);
    }
}
void get(int i,int l,int r,int u,int v,ii &res) {
    if (l>v) return;
    if (r<u) return;
    if ((u<=l) && (r<=v)) {
        res=max(res,t[i]);
        return;
    }
    get(2*i,l,(l+r)/2,u,v,res);
    get(2*i+1,(l+r)/2+1,r,u,v,res);
}
void update(int i,int l,int r,int x,int val) {
    if (l>x) return;
    if (r<x) return;
    if (l==r) {
        t[i]=ii(val,x);
        return;
    }
    update(2*i,l,(l+r)/2,x,val);
    update(2*i+1,(l+r)/2+1,r,x,val);
    t[i]=ii(val,x);
    if (x>l) get(1,1,n,l,x-1,t[i]);
    if (x<r) get(1,1,n,x+1,r,t[i]);
}
void process(void) {
    build(1,1,n);
    scanf("%d",&m);
    char c;
    int i,u,v;
    ii r1,r2;
    for (i=1;i<=m;i=i+1) {
        scanf("%c",&c);
        scanf("%c",&c);
        scanf("%d",&u);
        scanf("%d",&v);
        if (c=='U') update(1,1,n,u,v);
        else {
            r1=INF;
            r2=INF;
            get(1,1,n,u,v,r1);
            if (u<r1.p) get(1,1,n,u,r1.p-1,r2);
            if (r1.p<v) get(1,1,n,r1.p+1,v,r2);
            printf("%d\n",r1.v+r2.v);
        }
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Download