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.
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...
After that i just build a segment tree with lazy propagation.
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.
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.
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.
Thanks in advance.
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int mxN = 1e5 + 5;
vector<int> 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';
}
}
}