Hello guys..

I was trying to solve this task on SPOOJ but i am getting WA for some reason so hope if someone can help me..

The problem in-short asks you to find the count of prime number in specific interval which are also less than or equal to 1e7 after some modifications.

1. I just look for the primes until i reach 1e3, why? because i think if we are just looking for primes until 1e7 then we can check primes until square root of x only right? if it wasn't divisible by any prime then it's a prime number and i may be wrong...

2. After that i just build a segment tree with lazy propagation.

3. For propagation the count for specific interval with be either the length (rx — lx) or zero. depends if the new value will be a valid prime.

4. For a single point update i keep go down from the root until i reach to that point and it's count should be either 0 or 1.

5. Just calculate the count of sub-segment like any other segment tree, the count should refer to the number of valid items in my two halves.

I really don't know if this is a hard problem but it seems not and if my idea is correct then i believe my code has some bugs and i wish if someone can help since i am new to segment tree.

Here's my code and if it's not readable to you so i am sorry but i tried to make it look clean..

Gonna try to put the code here even though i never tried that before.

`#include

include

include

using namespace std;

const int mxN = 1e5 + 5; vector primes; int lazy[mxN * 4], a[mxN], n; bool vis[mxN];

struct node { int val; int cnt; } tree[mxN * 4];

bool is_prime(int x) { if(x == 1) return false; for(int p : primes) if(x % p == 0 && x != p) return false; return true; }

void propagate(int x, int lx, int rx) { if(lazy[x] == -1) return; tree[x].val = lazy[x]; tree[x].cnt = 0; if(lazy[x] <= 1e7 && is_prime(lazy[x])) tree[x].cnt = rx — lx; if(rx — lx == 1) { lazy[x] = -1; return; } lazy[2 * x + 1] = lazy[2 * x + 2] = lazy[x]; lazy[x] = -1; }

void build(int x = 0, int lx = 0, int rx = n) { if(rx — lx == 1) { tree[x].val = a[lx]; if(a[lx] <= 1e7) tree[x].cnt = is_prime(a[lx]); return; } int mid = (lx + rx) / 2; build(2 * x + 1, lx, mid); build(2 * x + 2, mid, rx); tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt; }

void update_point(int node, int v, int x = 0, int lx = 0, int rx = n) { propagate(x, lx, rx); if(rx — lx == 1) { tree[x].val += v; tree[x].cnt = 0; if(tree[x].val <= 1e7 && is_prime(tree[x].val)) tree[x].cnt = 1; return; } int mid = (lx + rx) / 2; if(node < mid) update_point(node, v, 2 * x + 1, lx, mid); else update_point(node, v, 2 * x + 2, mid, rx); tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt; }

void range_update(int l, int r, int v, int x = 0, int lx = 0, int rx = n) { propagate(x, lx, rx); if(lx >= l && rx <= r) { lazy[x] = v; propagate(x, lx, rx); return; } if(lx >= r || l >= rx) return; int mid = (lx + rx) / 2; range_update(l, r, v, 2 * x +1, lx, mid); range_update(l, r, v, 2 * x +2, mid, rx); tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt; }

int query(int l, int r, int x = 0, int lx = 0, int rx = n) { propagate(x, lx, rx); if(lx >= l && rx <= r) return tree[x].cnt; if(lx >= r || l >= rx) return 0; int mid = (lx + rx) / 2; int c1 = query(l, r, 2 * x + 1, lx, mid); int c2 = query(l, r, 2 * x +2, mid, rx); return c1 + c2; }

int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int q; cin >> n >> q; for(int i = 0; i < n; ++i) cin >> a[i]; memset(lazy, -1, sizeof lazy); for(int i = 2; i <= 1e3; ++i) { if(vis[i]) continue; primes.push_back(i); for(int j = i + i; j <= 1e3; j += i) vis[j] = true; } build(); while(q--) { char c; cin >> c; if(c == 'A') { int v, pos; cin >> v >> pos; --pos; update_point(pos, v); } else if(c == 'R') { int v, l, r; cin >> v >> l >> r; --l; range_update(l, r, v); } else { int l, r; cin >> l >> r; --l; cout << query(l, r) << '\n'; } } } ` Thanks in advance.