Ho fatto da poco le ds e sto trovando difficoltà con questo: ho provato un approccio con un segment tree ma va in TLE un po’ ovunque, consigli?
#include<bits/stdc++.h>
#define ninf INT_MIN
using namespace std;
struct ST{
struct node{
int val;
node() : val(ninf){}
void join(const node &l, const node &r){
val=max(l.val,r.val);
}
};
int real_size;
vector<node> nodes;
int size;
void cst(int n,vector<int> data){
size=n;
real_size=1;
while(real_size<n){
real_size*=2;
}
nodes.assign(2*real_size,node());
build(1,0,real_size,data);
}
void build(int u,int l,int r,vector<int> &data){
if(r-l==1){
if(l<data.size())
nodes[u].val=data[l];
}
else
{
build(2*u,l,(l+r)/2,data);
build(2*u+1,(l+r)/2,r,data);
nodes[u].join(nodes[2*u],nodes[2*u+1]);
}
}
void update(int pos,int x){
int u= real_size+pos;
nodes[u].val=x;
while(u>1){
u/=2;
nodes[u].join(nodes[2*u],nodes[2*u+1]);
}
}
int get_max(int u,int l,int r,int x,int y){
if(x>=r || y<=l) return ninf;
if(x<=l && y>=r) return nodes[u].val;
return max(
get_max(2*u,l,(l+r)/2,x,y),
get_max(2*u+1,(l+r)/2,r,x,y)
);
}
int get_max(int x,int y){
return get_max(1,0,real_size,x,y);
}
int spiasx(int l,int r,int h,int x){
if(get_max(l,r)<=h) return 0;
if(r-l==1) return l;
int a=spiasx((r+l)/2,r,h,x);
if(a!=0) return a;
int b=spiasx(l,(r+l)/2,h,x);
if(b!=0) return b;
return 0;
}
int spiadx(int l,int r,int h,int x){
if(get_max(l,r)<=h){
if(l==x+1 && r==real_size) return size-1;
else return 0;
}
if(l>=size) return 0;
if(r-l==1) return l;
int a=spiadx(l,(r+l)/2,h,x);
if(a!=0) return a;
int b=spiadx((r+l)/2,r,h,x);
if(b!=0) return b;
return size-1;
}
pair<int,int> spia(int x){
int a,b;
a=spiasx(0,x,nodes[real_size+x].val,x);
b=spiadx(x+1,real_size,nodes[real_size+x].val,x);
return {a,b};
}
};
ST st;
pair<int, int> chiedi(int x) {
return st.spia(x);
}
void cambia(int x, int h) {
st.update(x,h);
}
void inizializza(int N, vector<int> H) {
st.cst(N,H);
}
