Aiuto Rangetree1

Aiuto
1

Qualcuno può aiutarmi a risolvere rangetree1?
Ho provato con la tecnica della lazy propagation, però il caso di esempio mi esce sbagliato, ma non capisco perché!
Inoltre, sottomettendolo mi dice che esce dalla memoria.
Qualcuno ha idea di cosa possa essere?

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int N, Q;
int vettore[100100];
int segmentTree[100100], lazy[100100];
int K;

void lazyF(int startRange, int endRange, int delta, int low, int high, int pos)
{
    if(low > high)
        return;

    //propago

    if(lazy[pos] != 0)
    {
        segmentTree[pos] = -segmentTree[pos] +(high-low+1);
        if(high != low)
        {
            lazy[pos*2+1] == 0 ? lazy[pos*2+1] = 1 : lazy[pos*2+1] = 0;
            lazy[pos*2+2] == 0 ? lazy[pos*2+1] = 1 : lazy[pos*2+1] = 0;
        }
        lazy[pos] = 0;
    }

    //no overlap
    if(startRange > high || endRange < low)
        return;

    //total overlap

    if(startRange <= low && high <= endRange)
    {
        segmentTree[pos] = -segmentTree[pos] + (high-low+1);
        if(low != high)
        {
            lazy[pos*2+1] == 0 ? lazy[pos*2+1] = 1 : lazy[pos*2+1] = 0;
            lazy[pos*2+2] == 0 ? lazy[pos*2+1] = 1 : lazy[pos*2+1] = 0;

        }

        return;
    }

    //partial overlap

    int mid = (low + high)/2;
    lazyF(startRange, endRange, delta, low, mid, pos*2+1);
    lazyF(startRange, endRange, delta, mid+1, high, pos*2+2);

    segmentTree[pos] = segmentTree[pos*2+1] + segmentTree[pos*2+2];
}

int risposta(int startRange, int endRange, int low, int high, int pos)
{
    
    // Propago
    if(lazy[pos] != 0)
    {
        segmentTree[pos] = -segmentTree[pos] + (high-low+1);
        
        if(high != low)
        {
            lazy[pos*2+1] == 0 ? lazy[pos*2+1] = 1 : lazy[pos*2+1] = 0;
            lazy[pos*2+2] == 0 ? lazy[pos*2+1] = 1 : lazy[pos*2+1] = 0;
        }
        
        lazy[pos] = 0;
    }

    //no overlap

    if(startRange > high || endRange < low)
        return 0;


    //total overlap

    if(startRange >= low && high <= endRange)
        return segmentTree[pos];

    //partial overlap

    int mid = (low + high)/2;
    return risposta(startRange, endRange, low, mid, pos*2+1) + risposta(startRange, 
        endRange, mid + 1, high, pos*2+2);
}


int main()
{
    FILE *in, *out;
    in = freopen("input.txt", "r", stdin);
    out = freopen("output.txt", "w", stdout);
    scanf("%d %d", &N, &Q);
    K = N;
    while(sqrt(K) * sqrt(K) != K)
        K++;
    K = K*2-1;


    for(int i = 0; i < Q; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(a == 0)
        {
            lazyF(b,c,1,0,K,0);
        }

        else
        {
            cout << risposta(b,c,0,K,0) << endl;
        }
    }
    
    
}
2

Penso che esca dalla memoria perché per N = 100000 ti serve un segment tree grande il doppio, quando tu invece lo limiti a 100100

Se non ti funziona il caso di esempio ti va piuttosto bene, prova a debuggare il tuo codice e a vedere che cosa succede di diverso da quello che ti aspetti svolgendo l’algoritmo su carta :slight_smile:

1 Mi Piace
3

ATTENZIONE: l’errore sta nel fatto che, sicuramente nel copiare e incollare, non hai modificato la seconda riga del codice sottostante.

4

Ciao vedo che hai usato degli array di int (che occupano solitamente 4 byte), per ridurre la quantità di memoria utilizzata ti consiglio di usare degli array di bool per lazy[ ] oppure, anche se dubito servirà mai a qualcuno in uno di questi, un vector in cui ogni elemento occupa solamente 1 bit.

1 Mi Piace
5

Grazie a tutti! Avevo fatto un sacco di errori :c
(Per qualche strano motivo, ho dovuto creare un array lungo 400.000 anziché 200.000, probabilmente sbaglio a creare K :c)
Nel caso possa essere d’aiuto a qualcuno in futuro:

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int N, Q;
int segmentTree[400100]; bool lazy[400100];
int K;


void lazyF(int startRange, int endRange, int low, int high, int pos)
{

    if(low > high)
        return;

//cout << low << " " << high;
    //propago

    if(lazy[pos] != 0)
    {
        segmentTree[pos] = -segmentTree[pos] +(high-low+1);
        if(high != low)
        {
            lazy[pos*2+1] = !lazy[pos*2+1];
            lazy[pos*2+2] = !lazy[pos*2+2];
        }
        lazy[pos] = 0;
    }

//cout << startRange << " " << endRange << endl;

    //no overlap
    if(startRange > high || endRange < low)
        return;

    //total overlap


    if(startRange <= low && endRange >= high)
    {
        segmentTree[pos] = -segmentTree[pos] + (high-low+1);
        if(low != high)
        {
            lazy[pos*2+1] = !lazy[pos*2+1];
            lazy[pos*2+2] = !lazy[pos*2+2];
        }

        return;
    }

    //partial overlap

    int mid = (low + high)/2;
    lazyF(startRange, endRange, low, mid, pos*2+1);
    lazyF(startRange, endRange, mid+1, high, pos*2+2);

    segmentTree[pos] = segmentTree[pos*2+1] + segmentTree[pos*2+2];
}

int risposta(int startRange, int endRange, int low, int high, int pos)
{
    
//    stampa(segmentTree, K);
    // Propago

    if(low > high)
        return 0;

    if(lazy[pos] != 0)
    {
        segmentTree[pos] = -segmentTree[pos] + (high-low+1);
        
        if(high != low)
        {
            lazy[pos*2+1] = !lazy[pos*2+1];
            lazy[pos*2+2] = !lazy[pos*2+2];
        }
        
        lazy[pos] = 0;
    }

    //no overlap

    if(startRange > high || endRange < low)
        return 0;


    //total overlap

    if(startRange <= low && high <= endRange)
        return segmentTree[pos];

    //partial overlap

    int mid = (low + high)/2;

    return risposta(startRange, endRange, low, mid, pos*2+1) + risposta(startRange, 
        endRange, mid + 1, high, pos*2+2);
}


int main()
{
    FILE *in, *out;
    in = freopen("input.txt", "r", stdin);
    out = freopen("output.txt", "w", stdout);
    scanf("%d %d", &N, &Q);
    //K = N;
    
    for(K = 1; K < N; K += K);
    //while(int(sqrt(K)) * sqrt(K) != K)
        //K++;
    K = K*2-1;


    for(int i = 0; i < Q; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        //cout << a << b << c  << endl;
        if(a == 0)
        {
            lazyF(b,c,0,K,0);
        }

        else
        {
            cout << risposta(b,c,0,K,0) << endl;

        }
    }
    
    
}
1 Mi Piace
6

In effetti quando avevo studiato io i range tree, la regoletta era dichiarare un array lungo 4N. Li avevo studiati qui con google translate http://e-maxx.ru/algo/segment_tree

Penso sia per semplificare il codice, altrimenti con 2N devi fare un controllo aggiuntivo quando “pushi” i lazy update dalle foglie ai “figli delle foglie” che non esistono.

1 Mi Piace
7

teoricamente, non sarebbero 2N-1 nodi un rangetree?

8

Se fai 4 N non ti preoccupi di uscire fuori memoria con i lazy