【线段树】The 2021 ICPC Asia Regionals Online Contest (II)
2021-09-26 20:40:00 # ACM

题链

题目解析

题给两种操作：
  $1.$ $\forall i \in [L,R], x_i=x_i*w$；
  $2.$ 输出 $\sum_{i=l}^{r}f(x_i)$，其中 $f(x_i)$ 为 $x_i$ 的欧拉函数值；

由于 $f(x) = x * \prod_ { 质数 p\mid x} ( 1- \frac {1} {p} )$，对于一个数 $x = 6$，$x$ 的质因子有 $2$、$3$，$f(x) = 6 * \frac {1} {2} * \frac {2} {3} = 2$，那么将 $x$ 乘上 $w = 10$，由于 $w$ 的质因子有 $2$、$5$，其中 $2$ 这个质因子已经在 $x$ 中出现过了，那么 $x$ 乘上 $w$ 造成的贡献就是 $d = 10 * \frac {4} {5} = 8$，于是 $x = x * w = 60$，且 $f(60) = 2 * d = 16$；

用线段树维护出现的质因子和答案，每次修改暴力更新质因子是否存在，代码使用 $bitset$，好写还快；

代码实现

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ULL unsigned long long
	#define Pair pair<LL ,LL >
	#define ls rt<<1
	#define rs rt<<1|1
	#define PI acos(-1.0)
	#define eps 1e-8
	#define mod 998244353
	#define MAXN 50001
	#define MS 100005

int n,m,k;
struct node{
	bitset<111> c;
	int sum;
	int la;
}p[MS<<2];

bitset<111> change(int x){ // 求 x 的质因子 
	bitset<111> t; t.reset();
	for(int i=2;i*i<=x;i++){
		if(!(x%i)){
			t[i] = 1;
			while(!(x%i)) x/=i;
		}
	}
	if(x!=1) t[x] = 1;
	return t;
}

int cal(int w, bitset<111> t){ // 求贡献 
	for(int pos=t._Find_next(1); pos!=111; pos=t._Find_next(pos)) w = w/pos*(pos-1);
	return w;
}

void push_up(int rt){
	p[rt].sum = (p[ls].sum + p[rs].sum)%mod;
	p[rt].c = p[ls].c & p[rs].c;
}

void push_down(int rt){
	if(p[rt].la != 1){
		int t = p[rt].la;
		p[ls].sum = 1LL*p[ls].sum*t%mod;
		p[rs].sum = 1LL*p[rs].sum*t%mod;
		p[ls].la = 1LL*p[ls].la*t%mod;
		p[rs].la = 1LL*p[rs].la*t%mod;
		p[rt].la = 1;
	}
}

void build(int l,int r,int rt){
	p[rt].la = 1;
	if(l == r){
		int x; cin >> x;
		p[rt].c = change(x);
		p[rt].sum = cal(x,p[rt].c);
		return;
	}
	int m = l+r>>1;
	build(l,m,ls); build(m+1,r,rs);
	push_up(rt);
}

void modify(int L,int R,int l,int r,int rt,int w,bitset<111> cc){
	if(L <= l && r <= R){
		if((p[rt].c|cc) == p[rt].c){ // 如果该区间每个数的质因子都包含了 w 的质因子 
			p[rt].sum = 1LL*p[rt].sum*w%mod;
			p[rt].la = 1LL*p[rt].la*w%mod;
			return;
		} 
	}
	if(l == r){ // 暴力更新 
		bitset<111> t = (p[rt].c|cc)^p[rt].c;
		p[rt].sum = 1LL*p[rt].sum*cal(w,t)%mod;
		p[rt].c |= cc;
		return;
	}
	int m = l+r>>1;
	push_down(rt);
	if(m >= L) modify(L,R,l,m,ls,w,cc);
	if(m <  R) modify(L,R,m+1,r,rs,w,cc);
	push_up(rt);
}

int query(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R) return p[rt].sum;
	int m = l+r>>1, ans = 0;
	push_down(rt);
	if(m >= L) ans = (ans + query(L,R,l,m,ls) )%mod;
	if(m <  R) ans = (ans + query(L,R,m+1,r,rs) )%mod;
	return ans; 
}

void solve() {
	cin >> n >> m; build(1,n,1);
	while(m--){
		int op,l,r,w; cin >> op >> l >> r;
		if(!op) cin >> w, modify(l,r,1,n,1,w,change(w));
		else cout << query(l,r,1,n,1) << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	int ce = 1;
//	cin >> ce;
	while(ce--) {
		solve();
	}

	return 0;
}
/*


*/
Prev
2021-09-26 20:40:00 # ACM
Next