SPOJSolutions/CNTPRIME.cpp at master · pranavanurag/SPOJSolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>

using namespace std;

#define scan(x) scanf("%d", &x);

struct Node
{
	int Sum, Lazy;
	Node() {Sum = 0; Lazy = -1;}
};

Node SegTree[40001];
int T, N, Q, L, R, V, A[10001], IsQuery;
bool IsPrime[2000001];

void Refresh()
{
	for (int i = 0; i <= 40000; i++)
		SegTree[i] = Node();
}

void Seive()
{
	IsPrime[0] = IsPrime[1] = 0;
	for (int i = 2; i <= 2000000; i++)
		IsPrime[i] = 1;
	for (int i = 2; i <= 1415; i++)
		if (IsPrime[i])
			for (int j = i*i; j <= 2000000; j += i)
				IsPrime[j] = 0;
}

void PropogateLazy(int i, int STx1, int STx2)
{
	if (SegTree[i].Lazy != -1)
	{
		SegTree[i].Sum = (STx2 - STx1 + 1)*SegTree[i].Lazy;

		if (STx1 != STx2)
			SegTree[2*i].Lazy = SegTree[2*i + 1].Lazy = SegTree[i].Lazy;
		SegTree[i].Lazy = -1;
	}
}

void Build(int i, int STx1, int STx2)
{
	if (STx1 > STx2)
		return;
	if (STx1 == STx2)
		SegTree[i].Sum = A[STx1];
	else
	{
		int STxm = (STx1 + STx2)/2;
		Build(2*i, STx1, STxm);
		Build(2*i + 1, STxm + 1, STx2);
		SegTree[i].Sum = SegTree[2*i].Sum + SegTree[2*i + 1].Sum;
	}
}

void UpdateRange(int i, int STx1, int STx2, int x1, int x2, int V)
{
	PropogateLazy(i, STx1, STx2);

	if (x1 > x2 || STx1 > STx2 || x1 > STx2 || x2 < STx1)
		return;

	if (STx1 >= x1 && STx2 <= x2)
	{
		SegTree[i].Sum = (STx2 - STx1 + 1)*V;
		if (STx1 != STx2)
			SegTree[2*i].Lazy = SegTree[2*i + 1].Lazy = V;
	}
	else
	{
		int STxm = (STx1 + STx2)/2;
		UpdateRange(2*i, STx1, STxm, x1, x2, V);
		UpdateRange(2*i + 1, STxm + 1, STx2, x1, x2, V);
		SegTree[i].Sum = SegTree[2*i].Sum + SegTree[2*i + 1].Sum;
	}
}

Node Query(int i, int STx1, int STx2, int x1, int x2)
{
	PropogateLazy(i, STx1, STx2);
	if (x1 > x2 || STx1 > STx2 || x1 > STx2 || x2 < STx1)
		return Node();

	if (STx1 >= x1 && STx2 <= x2)
		return SegTree[i];
	int STxm = (STx1 + STx2)/2;
	Node Ans, Left = Query(2*i, STx1, STxm, x1, x2), Right = Query(2*i + 1, STxm + 1, STx2, x1, x2);
	Ans.Sum = Left.Sum + Right.Sum;
	return Ans;
}

int main()
{
	Seive();
	scan(T);
	for (int t = 1; t <= T; t++)
	{
		printf("Case %d:\n", t);
		Refresh();
		scan(N); scan(Q);
		for (int i = 1; i <= N; i++)
		{
			int temp;
			scan(temp);
			A[i] = (IsPrime[temp])?1:0;
		}
		Build(1, 1, N);
		while (Q--)
		{
			scan(IsQuery); scan(L); scan(R);
			if (IsQuery)
				printf("%d\n", Query(1, 1, N, L, R).Sum);
			else
			{
				scan(V);
				UpdateRange(1, 1, N, L, R, IsPrime[V]);
			}
		}
	}
	return 0;
}