RangeTree2 (Multiples of 3)

Aiuto
1

Dopo aver risolto Flipping Coins, ho provato a risolvere il suo successivo, cioè Multiples of 3 (rangetree2) applicando anche a esso il solito segment tree con la lazy propagation. Con il codice sottostante riesco solo a guadagnare 5 punti e volevo chiedere dove si trova il problema.

#include <bits/stdc++.h>

#define MAXN 1000100

using namespace std;

struct st
{
    int div1 = 0, div2 = 0, div3;
};

int N, Q;
st tree[MAXN];
int lazy[MAXN];

void update_tree(st tree[], int lazy[], int nodo, int inizio_seg, int fine_seg, int inizio_query, int fine_query)
{
    if(lazy[nodo] != 0)
    {
        if(tree[nodo].div1 == 0 && tree[nodo].div2 == 0 && tree[nodo].div3 == 0)
        {
            tree[nodo].div1 = fine_seg- inizio_seg +1;
        }
        else
        {
            for(int i = 0; i < lazy[nodo]; i++)
            {
                int div1 = tree[nodo].div1;
                int div2 = tree[nodo].div2;
                int div3 = tree[nodo].div3;

                tree[nodo].div1 = div3;
                tree[nodo].div2 = div1;
                tree[nodo].div3 = div2;
            }
        }

        if(inizio_seg != fine_seg)
        {
            lazy[nodo*2+1]++;
            lazy[nodo*2+2]++;
        }

        lazy[nodo] = 0;
    }

    if(inizio_seg > fine_query || fine_seg < inizio_query)
        return;

    if(inizio_seg >= inizio_query && fine_seg <= fine_query)
    {
        int div1 = tree[nodo].div1;
        int div2 = tree[nodo].div2;
        int div3 = tree[nodo].div3;

        tree[nodo].div1 = div3;
        tree[nodo].div2 = div1;
        tree[nodo].div3 = div2;

        if(inizio_seg != fine_seg)
        {
            lazy[nodo*2+1]++;
            lazy[nodo*2+2]++;
        }
        return;
    }

    int mid = (inizio_seg+fine_seg)/2;
    update_tree(tree, lazy, nodo*2+1, inizio_seg, mid, inizio_query, fine_query);
    update_tree(tree, lazy, nodo*2+2, mid+1, fine_seg, inizio_query, fine_query);

    tree[nodo].div1 = tree[nodo*2+2].div1 + tree[nodo*2+1].div1;
    tree[nodo].div2 = tree[nodo*2+2].div2 + tree[nodo*2+1].div2;
    tree[nodo].div3 = tree[nodo*2+2].div3 + tree[nodo*2+1].div3;

    return;
}

int sum_query(st tree[], int lazy[], int nodo, int inizio_seg, int fine_seg, int inizio_query, int fine_query)
{
    if(lazy[nodo] != 0)
    {
        if(tree[nodo].div1 == 0 && tree[nodo].div2 == 0 && tree[nodo].div3 == 0)
        {
            tree[nodo].div1 = fine_seg- inizio_seg +1;
        }
        else
        {
            for(int i = 0; i < lazy[nodo]; i++)
            {
                int div1 = tree[nodo].div1;
                int div2 = tree[nodo].div2;
                int div3 = tree[nodo].div3;

                tree[nodo].div1 = div3;
                tree[nodo].div2 = div1;
                tree[nodo].div3 = div2;
            }
        }

        if(inizio_seg != fine_seg)
        {
            lazy[nodo*2+1]++;
            lazy[nodo*2+2]++;
        }

        lazy[nodo] = 0;
    }

    if(inizio_seg > fine_query || fine_seg < inizio_query)
        return 0;

    if(inizio_seg >= inizio_query && fine_seg <= fine_query)
        return tree[nodo].div3;

    int mid = (inizio_seg+fine_seg)/2;
    return  sum_query(tree, lazy, nodo*2+1, inizio_seg, mid, inizio_query, fine_query) +
            sum_query(tree, lazy, nodo*2+2, mid+1, fine_seg, inizio_query, fine_query);
}

void create_tree(st tree[], int lazy[], int nodo, int inizio_seg, int fine_seg)
{
    if(inizio_seg == fine_seg)
    {
        tree[nodo].div3 = 1;
        return;
    }

    int mid = (inizio_seg+fine_seg)/2;
    create_tree(tree, lazy, nodo*2+1, inizio_seg, mid);
    create_tree(tree, lazy, nodo*2+2, mid+1, fine_seg);

    tree[nodo].div3 = tree[nodo*2+1].div3 + tree[nodo*2+2].div3;
    return;
}

int potenza_vicina(int N)
{
    int i;
    for(i = 1; i < N; i += i)
        ;
    return i;
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    scanf("%d %d", &N, &Q);

    int n = potenza_vicina(N);

    create_tree(tree, lazy, 0, 0, n-1);

    for(int i = 0; i < Q; i++)
    {
        int tipo, da, a;

        scanf("%d %d %d", &tipo, &da, &a);

        if(tipo == 0)
            update_tree(tree, lazy, 0, 0, n-1, da, a);
        else
            cout << sum_query(tree, lazy, 0, 0, n-1, da, a) << endl;
    }
    return 0;
}

P.S.: ho visto un topic omonimo (Rangetree2) e ho provato a confrontare il codice ma non vedo la differenza tra i due.

2

Prova a descrivere l’algoritmo che usi, i.e. come funziona il tuo rangetree

3

Quello che faccio è

  • crearmi il range tree iniziale (questo range tree è composto da 3 variabili, la variabile di modulo 1, modulo 2 e modulo 3);
  • quando vado ad aggiornare i vari nodi dei due alberi (range e lazy tree), incremento la variabile div1 se il nodo è settato a 0, senno eseguo delle rotazioni tra le tre variabili della struttura st;
  • se invece devo andare a controllare un range, verifico quanto vale nel nodo dell’albero la variabile div3 e la ritorno nella funzione.
4

la strategia è giusta

5

Scusate sapete dirmi dove sbaglio? (anche io faccio solo 5 punti)
https://pastebin.com/pYUJ8UC7