### Pancake's blog

By Pancake, 11 years ago, Hello :)

I'm trying to solve the KGSS problem on SPOJ . I implemented a segment tree data structure , and wrote a simple brute force to test my answers against. However , I keep getting WA. For any interval represented by a segment tree node , res[node] is the sum of highest two integers on that interval , and f[node] is the largest integer on that interval. Can anyone help ? Thanks a lot.

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 400004;
int N , Q;
int res[MAXN];
int f[MAXN];
int x[MAXN];

struct qstruct {
int a;
int b;
qstruct(int u , int v){
a = u;
b = v;
}
};

void update(int node , int s , int e , int qs , int qe , int val){
if(s > qe || e < qs)
return;
if(s >= qs && e <= qe){
f[node] = val;
return;
}
update(2 * node , s , (s + e)/2 , qs , qe , val);
update(2 * node + 1 , (s + e)/2 + 1 , e , qs , qe , val);
f[node] = max(f[2 * node] , f[2 * node + 1]);
res[node] = max(max(res[2 * node] , res[2 * node + 1]) , f[2 * node] + f[2 * node + 1]);
return;
}
qstruct query(int node , int s , int e , int qs , int qe){
if(s > qe || e < qs)
return qstruct(0 , 0);
if(s >= qs && e <= qe)
return qstruct(res[node] , f[node]);
qstruct q1 = query(2 * node , s , (s+e)/2 , qs , qe);
qstruct q2 = query(2 * node + 1 , (s+e)/2+1 , e , qs , qe);
qstruct q = qstruct(max(max(q1.a , q2.a) , q1.b + q2.b) , max(q1.b , q2.b));
return q;
}
void build_segment_tree(int node , int s , int e){
if(s == e){
f[node] = x[s];
return;
}
build_segment_tree(2 * node , s , (s + e) / 2);
build_segment_tree(2 * node + 1 , (s + e ) / 2 + 1 , e);
res[node] = max(max(res[2 * node] , res[2 * node + 1]) , f[2 * node] + f[2 * node + 1]);
f[node] = max(f[2 * node] , f[2 * node + 1]);
return;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d" , &N);
for(int n = 1 ; n <= N ; n++)
scanf("%d" , &x[n]);
build_segment_tree(1 , 1 , N);

scanf("%d" , &Q);
for(int q = 1 ; q <= Q ; q++){
char qtype;
int u , v;
cin >> qtype;
if(qtype == 'U'){
int idx , val;
scanf("%d %d" , &idx , &val);x[idx]=val;
update(1 , 1 , N , idx , idx , val);
}
else {
int u , v;
scanf("%d %d" , &u , &v);
printf("%d\n" , query(1 , 1 , N , u , v).a);
//int ans = 0;
//for(int i = u ; i < v ; i++)
//for(int j = i + 1  ; j<=v;j++)
//ans=max(ans,x[i]+x[j]);
//printf("BRUTE FORCE :%d\n",ans);
}
}
return 0;
} Comments (11)
| Write comment?
 » I think this "res[node] = max(max(res[2 * node] , res[2 * node + 1]) , f[2 * node] + f[2 * node + 1]);" should be "res[node] = max(max(res[2 * node] , res[2 * node + 1]) , min(f[2 * node], f[2 * node + 1]));", and the best sum is max(res[i]) + max(f[j]). If the maximum sum is a expression ai+aj = k, and ai > aj, aj > ap such that ap is any value different from aj and ai! So the problem asks you to find two values ai,aj such that they're the best values. So you can keep two variables, max and secmax, max[node] = max(max[left],max[right]), secmax[node] = max(secmax[left],secmax[right],min(max[left],max[right]), and the answer is max(max[i]) + secmax[j]) ( 0 < i <= n )! I got AC with this approach.
 » 11 years ago, # | ← Rev. 2 →   You may also try this approach: find the maximum element on the segment than update it as -inf, than find maximum again and print their sum. Dont forget to update the first maximum back to it's inital value. The only thing you need to implemen there is the simplest segment tree for getting minimum.
•  » » Thanks Rubanenko , your approach is interesting. But can anyone give me a testcase for which my original solution fails ? It's driving me mad :)
•  » » Although this is two years late, but what a brilliant approach!
•  » » » I'm glad that it was useful for you ^_^
•  » » Thanks Rubanenko!Your idea was awesome. Apart from this, the solution is incredibly fast.My code runs in ~70 ms
•  » » 5 years ago, # ^ | ← Rev. 2 →   How can I know idx of maximum element ?I know only its left or right in segment tree
•  » » » augmenting data structure
•  » » » » Will it Help me to know idx of maximum element in segment tree ?
•  » » » » » i am trying to show you how to fish stop asking for the fish.
•  » » » » » » But I am Trying in Segment Tree almost more than 2 hours And I Searched in google But I didn't find solution to find idx for Element