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 n, int index, int s, int e);
void stampa(struct nodo tree[], int n);
int query(struct nodo tree[], int n, int index, int a, int b);
void change(struct nodo tree[], int n, 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, 2*n,1,  n, 2*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, n*2, 1, a+n, b+n));
        else
            change(tree, n*2, 1, a+n, b+n);

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

void create(struct nodo tree[], int n, 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(index*2 < n){
        create(tree, n, index*2, s, s+(e-s-1)/2);
        create(tree, n, index*2+1, s+(e-s+1)/2, e);
    }
}

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

    if(a == tree[index].s && b == tree[index].e){
        tree[index].inverti = (tree[index].inverti+1)%2;
        tree[index].aggiornato = 0;
    }
    else{

        tree[index].aggiornato = 0;

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

            change(tree, n, index*2, a, tree[index*2].e);
            change(tree, n, index*2+1, tree[index*2+1].s, b);

        }
        else{

            if(b <= tree[index*2].e)
                change(tree, n, index*2, a, b);

            if(a >= tree[index*2+1].s)
                change(tree, n, index*2+1, a, b);

        }
    }

}


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

    if(a == tree[index].s && b == tree[index].e){
        if(tree[index].aggiornato == 1){
            return tree[index].value;
        }
        else{
            if(tree[index].inverti){
                if(index*2 < n){
                    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;
                }
                else{
                    tree[index].inverti = 0;
                    tree[index].value = (tree[index].value+1)%2;
                    tree[index].aggiornato = 1;
                    return tree[index].value;
                }
            }
            if(index*2 > n){
                tree[index].aggiornato = 1;
                return tree[index].value;
            }


            int c,d;
            c = query(tree, n, index*2, a, a + (b-a-1)/2);
            d = query(tree, n, index*2+1, a+(b-a+1)/2, b);

            tree[index].aggiornato = 1;
            tree[index].value = c+d;
            return tree[index].value;
        }
    }
    else{

        if(a <= tree[index*2].e && b >= tree[index*2+1].s){
            int c=0,d=0;

            c = query(tree, n, index*2, a, tree[index*2].e);
            d = query(tree, n, index*2+1, tree[index*2+1].s, b);

            return c+d;
        }
        else{
            int c=0,d=0;
            if(b <= tree[index*2].e)
                c = query(tree, n, index*2, a, b);

            if(a >= tree[index*2+1].s)
                d = query(tree, n, index*2+1, a, b);

            return c+d;
        }
    }
}

/*
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);
    }
}
*/