mydcwfy's Blog

CF1114F Please, another Queries on Array?

Posted on
Symbols count in article: 3.6k Reading time ≈ 8 mins.

题意：给定一个长度为 $n$ 的序列 $a$，修改为区间乘 $x$，询问为求 $\varphi(\prod_{i = l} ^ r a_i)$。$n\leq 4\times 10 ^ 5$，$q\leq 2\times 10 ^ 5$，$a_i, x\leq 300$。

首先考虑 $\varphi(n) = n\prod_p \dfrac{p - 1}p$，那么我们现在就相当于是需要知道所有数有没有每一个质数。我们发现 300 以内的数只有 62 个，这给了我们一定的启发。

首先线段树维护区间乘积肯定是必需的，另外，我们定义一个状态 $s$，表示包含了 $s$ 内的质数。容易发现这个修改时很好做的，也就是说我们只需要根据 $s$ 内部的状态乘上对应的 $\dfrac{p - 1}p$ 即可。

时间复杂度 $O(q\log n + (n + q)\dfrac{a}{\ln a})$，可以通过。

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
127
128
129
130
131
132
133
134
135
136
137
138
139
struct MulSegment {
	struct Node {
		int l, r;
		int res, lt;
	} tr[N << 2];
	
	void pushup(int x) { tr[x].res = (LL) tr[x << 1].res * tr[x << 1 | 1].res % Mod; }
	
	void build(int x, int l, int r)
	{
		tr[x] = {l, r, 0, 1};
		if (l == r) return tr[x].res = a[l], void();
		int mid = (l + r) >> 1;
		build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
		pushup(x);
	}
	
	void update(int x, int c)
	{
		tr[x].res = (LL) tr[x].res * qpow(c, tr[x].r - tr[x].l + 1) % Mod;
		tr[x].lt = (LL) tr[x].lt * c % Mod;
	}
	
	void pushdown(int x)
	{
		if (tr[x].lt == 1) return;
		update(x << 1, tr[x].lt), update(x << 1 | 1, tr[x].lt);
		tr[x].lt = 1;
	}
	
	void modify(int x, int l, int r, int c)
	{
		if (tr[x].l > r || tr[x].r < l) return;
		if (tr[x].l >= l && tr[x].r <= r) return update(x, c);
		pushdown(x);
		modify(x << 1, l, r, c), modify(x << 1 | 1, l, r, c);
		pushup(x);
	}
	
	int query(int x, int l, int r)
	{
		if (tr[x].l > r || tr[x].r < l) return 1;
		if (tr[x].l >= l && tr[x].r <= r) return tr[x].res;
		pushdown(x);
		return (LL) query(x << 1, l, r) * query(x << 1 | 1, l, r) % Mod;
	}
} seg1;

struct OrSegment {
	struct Node {
		int l, r;
		LL res, lt;
	} tr[N << 2];
	
	void pushup(int x) { tr[x].res = tr[x << 1].res | tr[x << 1 | 1].res; }
	
	void build(int x, int l, int r)
	{
		tr[x] = {l, r, 0, 0};
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
		pushup(x);
	}
	
	void update(int x, LL c) { tr[x].res |= c, tr[x].lt |= c; }
	
	void pushdown(int x) {
		if (!tr[x].lt) return;
		update(x << 1, tr[x].lt), update(x << 1 | 1, tr[x].lt);
		tr[x].lt = 0;
	}
	
	void modify(int x, int l, int r, LL c)
	{
		if (tr[x].l > r || tr[x].r < l) return;
		if (tr[x].l >= l && tr[x].r <= r) return update(x, c);
		pushdown(x);
		modify(x << 1, l, r, c), modify(x << 1 | 1, l, r, c);
		pushup(x);
	}
	
	LL query(int x, int l, int r)
	{
		if (tr[x].l > r || tr[x].r < l) return 0;
		if (tr[x].l >= l && tr[x].r <= r) return tr[x].res;
		pushdown(x);
		return query(x << 1, l, r) | query(x << 1 | 1, l, r);
	}
} seg2;

void sieve(int N = 301)
{
	for (int i = 2; i < N; ++ i)
	{
		if (!st[i]) prime[cnt ++] = i;
		for (int j = 0; j < cnt && i * prime[j] < N; ++ j)
		{
			st[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
	for (int i = 0; i < cnt; ++ i) invp[i] = qpow(prime[i]);
}

int main()
{
	sieve();
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	seg1.build(1, 1, n), seg2.build(1, 1, n);
	for (int i = 1; i <= n; ++ i)
	{
		LL s = 0;
		for (int j = 0; j < cnt && prime[j] <= a[i]; ++ j)
			if (a[i] % prime[j] == 0) s |= 1LL << j;
		seg2.modify(1, i, i, s);
	}
	char s[15];
	int l, r, x;
	while (m --)
	{
		scanf("%s%d%d", s, &l, &r);
		if (std::string(s) == "MULTIPLY") {
			scanf("%d", &x);
			LL s = 0;
			for (int j = 0; j < cnt; ++ j)
				if (x % prime[j] == 0) s |= 1LL << j;
			seg1.modify(1, l, r, x), seg2.modify(1, l, r, s);
		} else if (std::string(s) == "TOTIENT") {
			int res = seg1.query(1, l, r);
			LL s = seg2.query(1, l, r);
			for (int i = 0; i < 62; ++ i)
				if (s >> i & 1) res = (LL) res * invp[i] % Mod * (prime[i] - 1) % Mod;
			printf("%d\n", res);
		} else puts("Failed"), exit(0);
	}
	return 0;
}