rangetree1

#include <stdio.h>
#include<stdlib.h>
#include<math.h>

struct nodo{
    int s;
    int e;
    int value;
    int aggiornato;
    int inverti;
};

void create(struct nodo tree[], int index, int s, int e);
//void stampa(struct nodo tree[], int n);
int query(struct nodo tree[], int index, int a, int b);
void change(struct nodo tree[], int index, int a, int b);

main(){
    FILE *pF = fopen("input.txt", "r");
    int n,righe;
    fscanf(pF, "%d %d", &n, &righe);

    int i=0;
    while(n > pow(2,i))
        i++;

    while(n != pow(2,i))
        n++;
    struct nodo tree[2*n];
    create(tree, 1, 0, n-1);

    FILE *pF2 = fopen("output.txt", "w");
    int op, a, b;
    for(i=0; i<righe; i++){
        fscanf(pF, "\n%d %d %d", &op, &a, &b);

//      stampa(tree, 2*n);


        if(op==1)
            fprintf(pF2, "%d\n", query(tree, 1, a, b));
        else
            change(tree, 1, a, b);

//      stampa(tree, 2*n);
    }
    fclose(pF2);
    fclose(pF);
}

void create(struct nodo tree[], int index, int s, int e){

    tree[index].value = 0;
    tree[index].inverti = 0;
    tree[index].aggiornato = 1;
    tree[index].s = s;
    tree[index].e = e;

    if(s != e){
        create(tree, index*2, s, (s+e)/2);
        create(tree, index*2+1, (s+e)/2+1, e);
    }
}

void change(struct nodo tree[], int index, int a, int b){

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

    if(tree[index].s >= a && tree[index].e <= b){
        tree[index].inverti = (tree[index].inverti+1)%2;
        tree[index].aggiornato = 0;
        return; //non hai altro da fare in questo nodo
    }

    tree[index].aggiornato = 0;

    change(tree, index*2, a, b);
    change(tree, index*2+1, a, b);

}


int query(struct nodo tree[], int index, int a, int b){

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

    if(tree[index].s >= a && tree[index].e <= b){

        if(tree[index].aggiornato)
            return tree[index].value;
        else{
            if(tree[index].inverti){
                if(tree[index].s != tree[index].e){
                    tree[index].inverti = 0;
                    tree[index*2].inverti = (tree[index*2].inverti+1)%2;
                    tree[index*2+1].inverti = (tree[index*2+1].inverti+1)%2;
                    tree[index*2].aggiornato = 0;
                    tree[index*2+1].aggiornato = 0;

                    tree[index].value = query(tree, index*2, a, b) + query(tree, index*2+1, a, b);
                    tree[index].aggiornato = 1;
                    return tree[index].value;
                }
                else{
                    tree[index].inverti = 0;
                    tree[index].value = (tree[index].value+1)%2;
                    tree[index].aggiornato = 1;
                    return tree[index].value;
                }
            }

        }
    }

    if(tree[index].inverti){
        tree[index].inverti = 0;
        tree[index*2].inverti = (tree[index*2].inverti+1)%2;
        tree[index*2+1].inverti = (tree[index*2+1].inverti+1)%2;
        tree[index*2].aggiornato = 0;
        tree[index*2+1].aggiornato = 0;
    }

    tree[index].value = query(tree, index*2, a, b) + query(tree, index*2+1, a, b);
    tree[index].aggiornato = 1;
    return tree[index].value;
}

/*
void stampa(struct nodo tree[], int n){
    printf("\n\n");
    int i;
    int c = 1;
    for(i=1; i<n; i++){
        if(c == i){
            printf("\n");
            c *= 2;
        }
        printf("\nNodo %d, start = %d, end = %d, aggiornato = %d, inverti = %d, value = %d", i, tree[i].s, tree[i].e, tree[i].aggiornato, tree[i].inverti, tree[i].value);
    }
}
*/