Ciao, sto cercando di risolvere muraglia con un segment tree e, non avendo mai usato questa struttura, ho letto i vari argomenti sul forum su questo problema. Ho quindi implementato il segment basandomi su questo e ho aggiunto la funzione get_first da qui. Posto che devo ancora riscrivere il tutto per la sottoposizione, nemmeno copiando e incollando get_first riesco a ottenere i risultati giusti 
.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
struct segTree{
int N;
vector<ll> st;
segTree(vector<ll> &A) { //costruttore
N = A.size();
st.resize (4*N);
build(1,0,N,A); //chiamo la funzione build per inizializzare il segment tree
}
void call_update(int pos, ll newval){ //funzione per aggiornare il segment tree
update(1, 0, N, pos, newval);
}
int call_get_first(int pos, int val){
return get_first(1, 0, N-1, pos+1, N, val); //non sono sicuro di che valori passare in input
}
int call_get_last(int pos, int val){
return get_first(1, 0, N-1, 0, pos-1, val);
}
ll build (int i, int left, int right, vector<ll> &A) { // non da problemi
if (right - left == 1) {
return st[i] = A[left];
}
int mid = (left + right) / 2;
st[i] = max(build(2*i, left, mid, A), build(2*i+1, mid, right, A));
return st[i];
}
void update (int i, int left, int right, int pos, ll val) { // non da problemi
if (right - left == 1) {
st[i] = val;
return;
}
int mid = (left + right) / 2;
if (pos < mid) {
update (2*i, left, mid, pos, val);
}
else {
update (2*i+1, mid, right, pos, val);
}
st[i] = max(st[2*i],st[2*i+1]);
}
int get_first(int v, int lv, int rv, int l, int r, int x) {
if(lv > r || rv < l) return -1; // primo caso base: se il segment del nodo in cui sono è
// totalmente esterno al range [l..r] della query, allora non mi interessa
if(l <= lv && rv <= r) { // secondo caso base: se il nodo in cui sono è totalmente interno al range [l...r] distinguo due casi:
if(st[v] <= x) return -1; // 2.1) se non posso trovare un valore "utile" non mi interessa
while(lv != rv) { //2.2) se c'è un valore "utile" implemento una binary search per trovare quello più a sinistra
int mid = lv + (rv-lv)/2;
if(st[2*v] > x) {
v = 2*v;
rv = mid;
}else {
v = 2*v+1;
lv = mid+1;
}
}
return lv;
}
//se non ricado nei casi base continuo con la ricorsione
int mid = lv + (rv-lv)/2;
int rs = get_first(2*v, lv, mid, l, r, x); //scendo prima nel figlio di sinistra
if(rs != -1) return rs; //se il figlio di sinistra contiene un valore "utile" lo restituisco
return get_first(2*v+1, mid+1, rv, l ,r, x); //altrimenti devo scendere nel destro
}
int get_last(int v, int lv, int rv, int l, int r, int x) { //stessa funzione di get_first invertendo l'ordine con cui si scende nei figli
if(lv > r || rv < l) return -1;
if(l <= lv && rv <= r) {
if(st[v] <= x) return -1;
while(lv != rv) {
int mid = lv + (rv-lv)/2;
if(st[2*v+1] > x) {
v = 2*v+1;
lv = mid+1;
}else {
v = 2*v;
rv = mid;
}
}
return lv;
}
int mid = lv + (rv-lv)/2;
int ls = get_last(2*v+1, mid+1, rv, l, r, x);
if(ls != -1) return ls;
return get_last(2*v, lv, mid, l ,r, x);
}
};
int main()
{
vector<long long> A = {7, 4, 78, 2, 6, 4, 1, 9, 10, 7, 100, 56, 8, 1};
segTree maxst(A);
int a = 5;
cout << maxst.call_get_last(a, A[a-1]) <<" "<< maxst.call_get_first(a, A[a-1]) << endl; //non sono sicuro se passare A[a] (0 based) o A[a-1] (1-based)
return 0;
}
Immagino che il problema siano i valori passati in input alla funzione, ma anche con svariati tentativi non capisco innanzitutto se debba passare il valore di x 1-based (come il segment) o 0-based (come il vector), inoltre non credo che i valori che passo per lv, rv, l, r siano giusti. Aggiungendo o togliendo un elemento dal vettore A ottengo risultati diversi. 
PS non ho commentato le funzioni build e update perché non mi davano problemi, ma se serve posso aggiungere qualcosa anche per quelle.