Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement