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;
}