题目链接：点击打开链接
题意：有3种区间操作， 1是把区间内的所有数变成它的欧拉函数值， 2是把区间所有数都变成一个数x，3是查询区间和。
思路：后两个操作就是线段树的区间修改和求和， 没什么好说的。
题解说用平衡树（弱不会）， 不过大致思路线段树同样可以维护， 因为一个数进行最多phiO(logn)次就会变成1， 所以我们可以在递归结束，向上传标记的时候顺便看看其子区间是不是都等于1， 是就合并起来， 给这个点重新标记。
细节参见代码：
复制代码
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<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> using namespace std; typedef long long ll; typedef long double ld; const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795; const int mod = 1000000000 + 7; const int INF = int(1e9); const ll INF64 = ll(1e18); const int maxn = 300000 + 10; int T, n, m, v, id, l, r, x; ll sum[maxn<<2], setv[maxn<<2]; #define Max 10000010 ll euler[Max] = {0}; void Init(){ euler[1]=1; for(ll i=2;i<Max;i++) euler[i]=i; for(ll i=2;i<Max;i++) if(euler[i]==i) for(ll j=i;j<Max;j+=i) euler[j]=euler[j]/i*(i-1); } void PushUp(int o) { sum[o] = sum[o<<1] + sum[o<<1|1]; if(setv[o<<1] == setv[o<<1|1]) setv[o] = setv[o<<1]; else setv[o] = 0; } void build(int l, int r, int o) { int m = (l + r) >> 1; sum[o] = 0; setv[o] = 0; if(l == r) { scanf("%d",&v); sum[o] = setv[o] = v; return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); PushUp(o); } void pushdown(int l, int r, int o) { if(setv[o]) { int m = (l + r) >> 1; setv[o<<1] = setv[o<<1|1] = setv[o]; sum[o<<1] = (ll)(m - l + 1) * setv[o]; sum[o<<1|1] = (ll)(r - m) * setv[o]; setv[o] = 0; } } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { setv[o] = (ll)v; sum[o] = (ll)v * (r - l + 1); return ; } pushdown(l, r, o); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); PushUp(o); } void haha(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(setv[o] && L <= l && r <= R) { setv[o] = euler[setv[o]]; sum[o] = setv[o] * (r - l + 1); return ; } if(l == r) return ; pushdown(l, r, o); if(L <= m) haha(L, R, l, m, o<<1); if(m < R) haha(L, R, m+1, r, o<<1|1); PushUp(o); } ll query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; } pushdown(l, r, o); ll ans = 0; if(L <= m) ans += query(L, R, l, m, o<<1); if(m < R) ans += query(L, R, m+1, r, o<<1|1); PushUp(o); return ans; } int main() { Init(); scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); build(1, n, 1); while(m--) { scanf("%d%d%d",&id,&l,&r); if(id == 1) haha(l, r, 1, n, 1); else if(id == 2) { scanf("%d",&x); update(l, r, x, 1, n, 1); } else printf("%I64dn",query(l, r, 1, n, 1)); } } return 0; }
最后
以上就是现代老师最近收集整理的关于HDU 5634 Rikka with Phi（线段树）的全部内容，更多相关HDU内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复