Hello guys.. ↵
↵
I was trying to solve this [task](https://www.spoj.com/problems/PRMQUER/) 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](https://ideone.com/me023F) 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';↵
}↵
}↵
}↵
`↵
Thanks in advance.~~~~~↵
↵
↵
↵
I was trying to solve this [task](https://www.spoj.com/problems/PRMQUER/) 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](https://ideone.com/me023F) 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 <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
if(rx
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
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
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';↵
}↵
}↵
}↵
↵
↵
