2ndSequence's blog

By 2ndSequence, history, 4 years ago, In English

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.

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';
		}
	}
}

  • Vote: I like it
  • -7
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe just precompute isPrime[x] for all x (1 <= x <= 1e7): https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html#:~:text=Sieve%20of%20Eratosthenes%20is%20an,nloglogn)%20operations.&text=A%20proper%20multiple%20of%20a,this%20case%20it%20is%203. Then do the segment tree as you did. You can even do this before runtime and paste the results into your code.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes thank you i already did that as well but i still got WA.

    I used sieve to get the primes from [1, 1e3] but i was able to calculate it from [1, 1e7] and just ignore any value greater than 1e7..

    Do you think that it's just a bug in my code but the idea for the over-all solution is correct?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your primes code looks wrong (e.g. 1e3 < sqrt(1e7) so you may miss some primes). I used this for getting the primes:

      const int A = 1e7;
      void precompute() {
              isPrime = vector<bool>(A + 1, true);
              isPrime[0] = isPrime[1] = false;
              for (int i = 2; i * i <= A; i++) {
                  if (isPrime[i]) {
                      for (int j = i * i; j <= A; j += i) {
                          isPrime[j] = false;
                      }
                  }
              }
      }
      

      I also used segment tree with lazy propogation. I maintained the array tree and the original array a both.