KGSS - Maximum Sum
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define maxn 100011
#define oo 1111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i, a, b) for(int i = int(a); i <= int(b); i++)
#define FORD(i, a, b) for(int i = int(a); i >= int(b); i--)
//#include <conio.h>
//#define g 9.81
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}
double const PI=4*atan(1.0);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
void OPEN(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
}
struct tree{
int max1, max2;
tree(){};
tree(int _max1, int _max2){
max1 = _max1;
max2 = _max2;
}
};
tree empty = tree(-oo, -oo);
tree merge(tree T1, tree T2){
tree T;
if(T1.max1 > T2.max1) T = tree(T1.max1, max(T1.max2, T2.max1));
else T = tree(T2.max1, max(T2.max2, T1.max1));
return T;
}
tree T[maxn * 4];
int a[maxn];
int n, q, x, y;
char s[4];
void init(int l, int r, int i){
if(l == r){
T[i] = tree(a[l], 0);
return;
}
int mid = (l + r) / 2;
init(l, mid, i + i);
init(mid + 1, r, i + i + 1);
T[i] = merge(T[i + i], T[i + i + 1]);
}
void update(int l, int r, int i){
if(l > x || r < x) return;
if(l == r){
T[i] = tree(y, 0);
return;
}
int mid = (l + r) / 2;
update(l, mid, i + i);
update(mid + 1, r, i + i + 1);
T[i] = merge(T[i + i], T[i + i + 1]);
}
tree get(int l, int r, int i){
if(x > r || y < l) return empty;
if(x <= l && y >= r) return T[i];
int mid = (l + r) / 2;
return merge(get(l, mid, i + i), get(mid + 1, r, i + i + 1));
}
int main(){
// OPEN();
scanf("%d", &n);
FOR(i, 1, n) scanf("%d", &a[i]);
init(1, n, 1);
scanf("%d", &q);
rep(run, q){
scanf("%s %d %d", s, &x, &y);
if(s[0] == 'Q'){
tree res = get(1, n, 1);
printf("%d\n",res.max1 + res.max2);
}
else update(1, n, 1);
}
}