Grande muraglia 10/100 con Segment tree

Aiuto
1

Ho provato a scrivere grande muraglia con un segment tree, ma fa solo 10/100. La query del problema è quella di trovare in un array il range entro il quale tutti i numeri sono <= ad un numero ad una certa posizione x(gli estremi sono i primi numeri che sono > al numero). Credo ci sia qualche problema di ottimizzazione, ma non saprei. Ho già provato a calcolare l’estremo destro e quello sinistro in un colpo solo ma non è servito.

#include <bits/stdc++.h>
using namespace std;

vector<int> ST;
int dimensione;
int elementi;
//cout vector
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v){
    o << "[ ";
    for(auto i: v){
        o << i << " ";
    }
    o << "]";
    return o;
};
pair<int, int> chiedi(int x) {
  int rx = dimensione + x;
  int h = ST[rx];

  stack<pair<int, pair<int, int>>> S;
  S.push({1, {0, dimensione}});

  pair<int, pair<int, int>> curr;
  int a=0;

  while (not S.empty()){
    curr = S.top();
    S.pop();

    if(curr.first == rx) continue;

    else if(curr.second.second < a) continue;

    else if(ST[curr.first] <= h) continue;
    else{
      if(curr.first < dimensione){
        int middle = (curr.second.first + curr.second.second)/2;
        if(middle < x){
          S.push({curr.first*2 + 1, {middle + 1, curr.second.second}}); 
          S.push({curr.first*2, {curr.second.first, middle}});
        }else{
          S.push({curr.first*2, {curr.second.first, middle}});
        }
      }else{
        curr.first -= dimensione;
        if((a < curr.first) and (curr.first < x)){
          a = curr.first;

        }
        curr.first += dimensione;

      }
    }
  }

  S.empty();
  S.push({1, {0, dimensione}});
  int b=elementi - 1;
  while (not S.empty()){
    curr = S.top();
    S.pop();

    if(curr.first == rx) continue;

    else if(b < curr.second.first) continue;

    else if(ST[curr.first] <= h) continue;
    else{
      if(curr.first < dimensione){
        int middle = (curr.second.first + curr.second.second)/2;
        if(middle < x){
          S.push({curr.first*2 + 1, {middle + 1, curr.second.second}}); 
        }else{
          S.push({curr.first*2, {curr.second.first, middle}});
          S.push({curr.first*2 + 1, {middle + 1, curr.second.second}}); 
        }
      }else{
        curr.first -= dimensione;
        if((x < curr.first) and (curr.first < b)){
          b = curr.first;

        }
        curr.first += dimensione;
      }
    }
  }

  return {a, min(b, elementi - 1)};
}

void cambia(int x, int h) {
  int pos = dimensione + x;

  ST[pos] = h;
  pos /= 2;

  while((pos > 0) and ST[pos] < h){
    ST[pos] = h;
    pos /= 2;
  }

  return;
}

void inizializza(int N, vector<int> H) {
  dimensione = 1;
  elementi = H.size();
  while(dimensione < elementi)
    dimensione *= 2;

  ST = vector<int>(2*dimensione, numeric_limits<int>::min());
  
  int livello = dimensione;

  copy(H.begin(), H.end(), ST.begin()+livello);

  while(livello > 1){
    for(int i=livello+1; i<=(2 * livello); i++){
      if(ST[i] > ST[i/2]){
        ST[i/2] = ST[i];
      }
    }

    livello /= 2;
  }

	return;
}

Grazie Mille

2

Ciao, usare un segment tree è il giusto modo per risolvere muraglia. Però devi implementarlo più efficientemente: ti consiglio di consultare questo sito per avere un esempio di buona implementazione di segment tree.

Suggerimento: invece di fare questo, puoi dichiarare dimensione come 2 elevato alla \lceil log_2 N \rceil (in C++: ceil(log2(N));).
P.S. 2^x in C++ è 1 << x;

Spero di essere stato d’aiuto!

3

Grazie Mille!
Ci ho provato e ho ottenuto 25/100 (Mi è uscito il 4° subtask), probabilmente c’è ancora qualche bug. Ci provo ancora per qualche giorno e poi se non riesco ti chiedo di nuovo.

Grazie ancora!

4

image

Grazie Mille!

Ho trovato un paio di bug un po’ ovunque ma alla fine ho più o meno risolto.
Solo una cosa: volevo provare a implemetare chiedi in modo iterativo, per ora ma mi è uscito solo ricorsivo. Qualche suggerimento? Grazie Mille.

Il mio tentativo era stato:

void cambia(int x, int h) {
  int pos = dimensione + x;

  d(ST); 
  d(x); d(h);
  do{
    ST[pos] = h;
    pos /= 2;
  }while((pos != 1) and ((h>ST[pos*2]) and (h>ST[pos*2+1])));

  d(ST);
  return;
}

La mia implementazione attuale è:

struct Node{
  int index;
  pair<int, int> range;

  int get_middle(){
    return (this -> range.first + this -> range.second)/2;
  }
};

void cambia(Node n, int x, int h){
  if(n.range.first == n.range.second){
    ST[n.index] = h;
  }
  else{
    int middle = n.get_middle();
    if(x <= middle){
      cambia({n.index*2, {n.range.first, middle}}, x, h);
    }else{
      cambia({n.index*2+1, {middle+1, n.range.second}}, x, h);
    }

    ST[n.index] = max(ST[n.index*2], ST[n.index*2+1]);
  }
}


void cambia(int x, int h) {
  int pos = dimensione + x;

  cambia({1, {0, dimensione - 1}}, x, h);

  return;
}
5

codice finale:

#include <bits/stdc++.h>
#define d(x) //cerr << __LINE__ << ": " << #x << " = " << x << endl
using namespace std;

vector<int> ST;
int dimensione;
int elementi;
int counter = 0;

//cout ST
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v){
  int c = -1;
  int limit = 1;
  o << "\n";
  for(auto i: v){
    if(c == limit){
      limit *= 2;
      c = 0;
      o << "\n";
    }
    o << i << " ";
    c++;
  }
  return o;
};

struct Node{
  int index;
  pair<int, int> range;

  int get_middle(){
    return (this -> range.first + this -> range.second)/2;
  }
};


ostream& operator<<(ostream& o, const Node& v){
  o << v.index << " {" << v.range.first << ", " << v.range.second << "}";
  return o;
}

int left_limit(int h, int x){
  stack<Node> S;
  S.push({1, {0, dimensione-1}});

  Node curr;

  while (not S.empty()){
    curr = S.top();
    S.pop();

    if(curr.index >= 2*dimensione) continue;

    if(ST[curr.index] <= h){
      continue;
    }else if(x <= curr.range.first){
      continue;
    }else if(curr.range.second <= x){
      while(curr.range.first != curr.range.second){
        int middle = curr.get_middle();
        if(ST[2*curr.index + 1] > h){
          curr = {2*curr.index + 1, {middle + 1, curr.range.second}};
        }else{
          curr = {2*curr.index, {curr.range.first, middle}};
        }
      }
      if(ST[curr.index] > h){
        return curr.range.first;
      }
    }
    int middle = curr.get_middle();
    S.push({2*curr.index, {curr.range.first, middle}});
    S.push({2*curr.index + 1, {middle + 1, curr.range.second}});
  }
  return 0;
}

int right_limit(int const h, int const x){
  stack<Node> S;
  S.push({1, {0, dimensione-1}});

  Node curr;

  while (not S.empty()){
    curr = S.top();
    S.pop();
    
    if(curr.index >= 2*dimensione) continue;

    if(ST[curr.index] <= h){
      continue;
    }else if(curr.range.second <= x){
      continue;
    }else if(x <= curr.range.first){
      while(curr.range.first != curr.range.second){
        int middle = curr.get_middle();
        if(ST[2*curr.index] > h){
          curr = {2*curr.index, {curr.range.first, middle}};
        }else{
          curr = {2*curr.index + 1, {middle + 1, curr.range.second}};
        }
      }
      if(ST[curr.index] > h){
        return curr.range.first;
      }
    }else{
      int middle = curr.get_middle();
      S.push({2*curr.index + 1, {middle + 1, curr.range.second}});
      S.push({2*curr.index, {curr.range.first, middle}});
    }
  }
  return elementi - 1;
}

pair<int, int> chiedi(int x) {
  counter++;
  int rx = dimensione + x;
  int h = ST[rx];

  return {left_limit(h, x), right_limit(h, x)};
}

void cambia(Node n, int x, int h){
  if(n.range.first == n.range.second){
    ST[n.index] = h;
  }
  else{
    int middle = n.get_middle();
    if(x <= middle){
      cambia({n.index*2, {n.range.first, middle}}, x, h);
    }else{
      cambia({n.index*2+1, {middle+1, n.range.second}}, x, h);
    }

    ST[n.index] = max(ST[n.index*2], ST[n.index*2+1]);
  }
}


void cambia(int x, int h) {
  int pos = dimensione + x;

  cambia({1, {0, dimensione - 1}}, x, h);

  return;
}

void inizializza(int N, vector<int> H) {
  elementi = H.size();
  dimensione = 2 << ((int)ceil(log2(elementi)) - 1);
  ST = vector<int>(2*dimensione, numeric_limits<int>::min());
  copy(H.begin(), H.end(), ST.begin()+dimensione);

  int i = (dimensione + elementi)/2;
  do{
    ST[i] = max(ST[2*i], ST[2*i+1]);
    i--;
  }while(i > 0);

  return;
}
1 Mi Piace