numbers_tre_Adrian

/**
am afisat si arborele si raspunsurile la operatii cu tab*/
#include <bits/stdc++.h>///nu ....nr. compuse 0 si prime 1
#define MAX 1000001      /// nu memorez numerele ci 1 pentru prime si 0 pt. compuse
#define NMAX 100005         /// pentru operatia 3 nu stiu cum sa fac ...
using namespace std;
ifstream fin("numbers_tree.in");
ofstream fout("numbers_tree.out");
int n, ar[NMAX], Q,t;
bool isPrime[MAX];
int tree[4*NMAX];
void sieveOfEratosthenes(bool isPrime[])
{
    isPrime[0]=isPrime[1] = false;
    for(int p = 2; p * p <= MAX; p++)
    {
        if (isPrime[p] == true)
            for(int i = p * 2; i <= MAX; i += p)
                isPrime[i] = false;
    }
}
void showSegTree(int n)  /// afisat pe nivele ...
{
    int i, j, h = ceil(log2(n));
    for(i=0 ; i<=h ; ++i)
    {
        for(j=0 ; j<pow(2, i) ; ++j)
            cout<<tree[int(pow(2, i)-1 + j)]<<' ';
        cout<<'\n';
    }
    cout<<"\n_______________________\n";
}
int getMid(int s, int e)
{
    return s + (e - s) / 2;
}
int queryCompositesUtil(int st[], int ss, int se, int qs, int qe, int index)
{
    if (qs <= ss && qe >= se)
        return st[index];
    if (se < qs || ss > qe)
        return 0;
    int mid = getMid(ss, se);
    return queryCompositesUtil(st, ss, mid, qs, qe, 2 * index + 1)
           + queryCompositesUtil(st, mid + 1, se, qs, qe, 2 * index + 2);
}
void queryComposites(int st[], int n, int qs, int qe)
{
    int compositesInRange = queryCompositesUtil(st, 0, n - 1, qs, qe, 0);
    if(t==2)
        cout << '\t' <<(qe - qs +1) - compositesInRange << "\n";
    else
        cout << '\t' << compositesInRange<<'\n';
}
int constSegTree(int strt, int endi, int idx)
{
  /// Saves tree[idx] = ar[strt] and then returns tree[idx]
    if(strt == endi)
        return tree[idx] = ar[strt];
    int mid = (strt + endi) / 2;
    return tree[idx] = constSegTree(strt, mid, 2*idx+1) +
            constSegTree(mid+1, endi, 2*idx+2);
}
void ConstSegTree(int n)
{
    constSegTree(0, n-1, 0);
}
void updtRange(int strt, int endi, int val, int l, int r, int idx)
{
  /// Completly ouside the desired range
    if(endi < l || r < strt || l>r)
        return;
  /// Leaf node reached
    if(l == r)
    {
        tree[idx] = val;  /// Update the leaves
        return;
    }
    int mid = (l + r) / 2;
    updtRange(strt, endi, val, l, mid, 2*idx+1);
    updtRange(strt, endi, val, mid+1, r, 2*idx+2);
  /// Update the intermediate nodes
    tree[idx] = tree[2*idx+1] + tree[2*idx+2];
}
void UpdtRange(int n, int strt, int endi, int val)
{
    updtRange(strt, endi, val, 0, n-1, 0);
}
int main()
{
    int i, j, x;
    memset(isPrime, true, sizeof isPrime);
    sieveOfEratosthenes(isPrime);
    fin >> n >> Q;
    for(i = 0; i < n; i++)
    {
        fin >> x;
        if(isPrime[x])
            ar[i]=1;
    }
    ConstSegTree(n);
    while(Q--)
    {
        fin >> t;
        if(t == 1)
        {
            fin >> i >> j >> x;
            if(isPrime[x])
                UpdtRange(n,i-1,j-1,1);
            else
                UpdtRange(n,i-1,j-1,0);
            showSegTree(n);
        }
        else ///if(t==2)   /// AICI PENTRU t==2 CRED CA AFISEAZA CORECT, DAR pt. t==3 AFISEAZA TOTAL PRIME IN RANGE
        {
            fin >> i >> j;
            queryComposites(tree,n,i-1,j-1);
        }
    }
    return 0;
}