Rangetree2

Aiuto
1

Ciao a tutti, stavo provando a risolvere i problemi con i range trees, ma in alcuni casi per rangetree2 vado in Execution Timed Out. 

Ho utilizzato (ovviamente) un range tree e la lazy propagation per l’update, quindi non capisco quale possa essere il problema. Ho sbagliato l’implementazione della lazy? O ho implementato il range tree in un modo così inefficiente?


#include <iostream>

#include <fstream>

using namespace std;


struct nodo

{

int s, e;   //inizio e fine del segmento, s == e per i figli

int lazy;   //flag per l’update

int mod0;   //mod0 = n%3 = 0, mod1 = n%3 = 1, mod2 = n%3 = 2

int mod1;

int mod2;

};


void build_tree(int s, int e, int index, nodo tree[])

{

tree[index].s = s;

tree[index].e = e;

tree[index].lazy = 0;

tree[index].mod0 = tree[index].e - tree[index].s + 1;

tree[index].mod1 = tree[index].mod2 = 0;


if(s == e) return;

build_tree(s, s + (e-s)/2, 2*index, tree);
build_tree(s + (e-s)/2+1, e, 2*index+1, tree);



}


void rotate(int &mod0, int &mod1, int &mod2)

{

int c = mod0;

int l = mod1;


mod0 = mod2;
mod1 = c;
mod2 = l;



}


void add_one(int s, int e, int index, nodo tree[])

{

if(tree[index].lazy > 0)

{

for(int i = 0; i < tree[index].lazy; i++)

rotate(tree[index].mod0, tree[index].mod1, tree[index].mod2);


if(tree[index].s != tree[index].e)
{
    tree[index*2].lazy += tree[index].lazy;
    tree[index*2+1].lazy += tree[index].lazy;
}

tree[index].lazy = 0;
}

if(tree[index].s &gt; e || tree[index].e &lt; s) return;

if(tree[index].s &gt;= s &amp;&amp; tree[index].e &lt;= e)
{
rotate(tree[index].mod0, tree[index].mod1, tree[index].mod2); 

if(tree[index].e != tree[index].s)
{
    tree[index*2].lazy++;
    tree[index*2+1].lazy ++;
}
return;
}

add_one(s, e, index*2, tree);
add_one(s, e, index*2+1, tree);   

tree[index].mod0 = tree[index*2].mod0 + tree[index*2+1].mod0;
tree[index].mod1 = tree[index*2].mod1 + tree[index*2+1].mod1;
tree[index].mod2 = tree[index*2].mod2 + tree[index*2+1].mod2;



}


int query(int s, int e, int index, nodo tree[])

{

if(tree[index].s > e || tree[index].e < s) return 0;


if(tree[index].lazy &gt; 0)
{
for(int i = 0; i &lt; tree[index].lazy; i++)
    rotate(tree[index].mod0, tree[index].mod1, tree[index].mod2);

if(tree[index].s != tree[index].e)
{
    tree[index*2].lazy += tree[index].lazy;
    tree[index*2+1].lazy += tree[index].lazy;
}

tree[index].lazy = 0;
}

if(tree[index].s &gt;= s &amp;&amp; tree[index].e &lt;= e)
return tree[index].mod0;

return query(s, e, index*2, tree) + query(s, e, index*2+1, tree);



}


/*void print_tree(int index, nodo tree[])

{

cout << “[” << tree[index].s << ", " << tree[index].e << "] " << tree[index].mod0 << “\n”;


if(tree[index].e == tree[index].s) return;

print_tree(index*2, tree);
print_tree(index*2+1, tree);



}*/


int main()

{

ifstream in(“input.txt”);

ofstream out(“output.txt”);


int N, Q;

in &gt;&gt; N &gt;&gt; Q;

int dim = 2;

while(dim &lt; 2*N)
dim *= 2;

nodo rtree[dim];

build_tree(0, N-1, 1, rtree);

//print_tree(1, rtree);

int com, s, e;
for(int i = 0; i &lt; Q; i++)
{
in &gt;&gt; com &gt;&gt; s &gt;&gt; e;
if(com == 0)
    add_one(s, e, 1, rtree);
else
    out &lt;&lt; query(s, e, 1, rtree) &lt;&lt; endl;
}

// cout &lt;&lt; "End of input\n";

// print_tree(1, rtree);

return 0;



}
2

Invece di ruotare tante volte quanto è tree[nodo].lazy, puoi fare un bel lazy%3 e ruotare 1 volta se 1 e 2 volte se 2 :wink:


Ah, io non terrei  nel nodo l’inizio e la fine del nodo… credo che sia solo uno spreco di memoria…

P.S: invece di ruotare anche nell’add_one, incrementa il lazy di 1… Che bisogno ho i ruotare sempre ,quando magari con 3 query uguali torno alla situazione iniziale?
3

100/100… Ci avevo pure pensato ma mi è passato completamente di mente :lol:


E dove dovrei memorizzarlo?
4

direttamente nella funzione. Ad esempio la mia funzione per rangetree2:

void add(int pos,int A,int B,int inizio,int fine)
{
    if(A>fine || B<inizio) return;
    if(A<=inizio && B>=fine) {tree[pos].somma++; return;}


    add(pos2,A,B,inizio,(inizio+fine)/2);
    add(pos2+1,A,B,(inizio+fine)/2+1,fine);


    update_node(query(pos2,inizio,(inizio+fine)/2,inizio,(inizio+fine)/2,0),query(pos2+1,(inizio+fine)/2+1,fine,(inizio+fine)/2+1,fine,0),&tree[pos]);
}

Praticamente A e B sono inizio e fine del range della query, mentre inizio e fine sono quelli del range del nodo in posizione “pos”… Io ho imparato così a fare i rangetree, e senza utilizzare tutti quei “lazy” (o magari li ho rinonimati in altro modo aahahah)

5

Adesso provo un po’, vedo se ci sono miglioramenti

EDIT: Guadagno di 0.02 nei tempi e di 2 MB nell’utilizzo di memoria. Grazie mille :smiley:

6
Adesso provo un po', vedo se ci sono miglioramenti

EDIT: Guadagno di 0.02 nei tempi e di 2 MB nell'utilizzo di memoria. Grazie mille :D

Degiac

Non molto, ma era più che altro per avere meno variabili nella struct e per conservare solo ciò che serve ;)