I am working on this problem for 13+ hours. I read on the discussion that it would require two segment tree and now, I am not getting what is wrong with my code. Though it passes test-cases and I think the main problem must be where I trying to find the median.
#include <bits/stdc++.h>
#define ull unsigned long long int
#define ll long long int
#define P pair
#define V vector
#define S set
#define MS multiset
#define M map
#define MM multimap
#define IT iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
using namespace std;
class SEGMENT_TREE{
ll *arr;
ll n;
ll *tree;
ll treeheight;
public:
SEGMENT_TREE(ll *A, ll n){
this->arr = A;
this->n = n;
ll tmp = this->n;
ll count = 0;
while(tmp){
count+=tmp;
tmp/=2;
}
this->tree = (ll*)calloc(count*2,sizeof(ll));
this->treeheight = 0;
}
void build_sum_tree(ll node, ll start, ll end);
void update_sum_tree(ll node, ll start, ll end, ll index, ll value);
ll query_sum_tree(ll node, ll start, ll end, ll left_index, ll right_index);
void build_max_tree(ll node, ll start, ll end);
void update_max_tree(ll node, ll start, ll end, ll index, ll value);
ll query_max_tree(ll node, ll start, ll end, ll left_index, ll right_index);
void display_tree();
void display_array();
};
void SEGMENT_TREE::build_sum_tree(ll node, ll start, ll end){
if(node > treeheight)treeheight=node;
if(start == end){
tree[node] = arr[start];
}else{
ll mid = start + (end-start)/2;
build_sum_tree(2*node,start,mid);
build_sum_tree(2*node+1,mid+1,end);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
void SEGMENT_TREE::update_sum_tree(ll node, ll start, ll end, ll index, ll value){
if(start == end){
arr[index] = value;
tree[node] = value;
}else{
ll mid = start + (end-start)/2;
if(start <= index && index <= mid)update_sum_tree(2*node,start,mid,index,value);
else update_sum_tree(2*node+1,mid+1,end,index,value);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
ll SEGMENT_TREE::query_sum_tree(ll node, ll start, ll end, ll left_index, ll right_index){
if(right_index < start || left_index > end)return 0;
if(left_index <= start && right_index >= end)return tree[node];
//If case is none of the above then,
ll mid = start + (end-start)/2;
ll p1 = query_sum_tree(2*node,start,mid,left_index,right_index);
ll p2 = query_sum_tree(2*node+1,mid+1,end,left_index,right_index);
return p1 + p2;
}
void SEGMENT_TREE::build_max_tree(ll node, ll start, ll end){
if(node > treeheight)treeheight=node;
if(start == end){
tree[node] = start;
}else{
ll mid = start + (end-start)/2;
build_max_tree(2*node,start,mid);
build_max_tree(2*node+1,mid+1,end);
tree[node] = (arr[tree[2*node]] > arr[tree[2*node+1]])?tree[2*node]:tree[2*node+1];
}
}
void SEGMENT_TREE::update_max_tree(ll node, ll start, ll end, ll index, ll value){
if(start == end){
arr[index] = value;
tree[node] = index;
}else{
ll mid = start + (end-start)/2;
if(start <= index && index <= mid)update_max_tree(2*node,start,mid,index,value);
else update_max_tree(2*node+1,mid+1,end,index,value);
tree[node] = (arr[tree[2*node]] > arr[tree[2*node+1]])?tree[2*node]:tree[2*node+1];
}
}
ll SEGMENT_TREE::query_max_tree(ll node, ll start, ll end, ll left_index, ll right_index){
if(right_index < start || left_index > end)return 0;
if(left_index <= start && right_index >= end)return tree[node];
//If case is none of the above then,
ll mid = start + (end-start)/2;
ll p1 = query_max_tree(2*node,start,mid,left_index,right_index);
ll p2 = query_max_tree(2*node+1,mid+1,end,left_index,right_index);
if(p1 == 0)return p2;
if(p2 == 0)return p1;
return (arr[p1]>arr[p2])?p1:p2;
}
void SEGMENT_TREE::display_tree(){
for(ll i = 1; i <= treeheight; ++i){
cout << tree[i] << " ";
if(i%20 == 0)cout << endl;
}
}
void SEGMENT_TREE::display_array(){
for(ll i = 1; i <= n; ++i){
cout << arr[i] << " ";
if(i%20 == 0)cout << endl;
}
}
ll gcd(ll a, ll b){
if(a == 0)return b;
return gcd(b%a,a);
}
ll lcm(ll a, ll b){
return (a*b)/gcd(a,b);
}
int main(){
FAST
ll t;
cin >> t;
while(t--){
ll n,q;
cin >> n >> q;
ll *arr = new ll[n+1];
for(ll i = 1; i <= n; ++i)cin >> arr[i];
SEGMENT_TREE mode(arr,n);
SEGMENT_TREE median(arr,n);
mode.build_max_tree(1,1,n);
median.build_sum_tree(1,1,n);
while(q--){
ll a,b,c;
cin >> a >> b >> c;
if(a == 2){
mode.update_max_tree(1,1,n,b,c);
median.update_sum_tree(1,1,n,b,c);
}else{
ll mo = mode.query_max_tree(1,1,n,b,c);
ll elements = median.query_sum_tree(1,1,n,b,c);
ll tmp = elements;
ll med;
if(elements%2==0)elements++;
elements/=2;
while(elements-arr[b] > 0){
elements-=arr[b++];
}
med = b;
if(tmp%2 == 0){
if(elements - arr[b]<1){
b++;
while(arr[b]==0)b++;
}
med+=b;
med/=2;
}
cout << lcm(med,mo) << endl;
}
}
}
return 0;
}