Submission #69053

ソースコード

?
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
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
using namespace std;
template< typename Monoid, typename F >
struct SegmentTree {
int sz;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) {
seg[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while(k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) L = f(L, seg[a++]);
if(b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const {
return seg[k + sz];
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return -1;
}
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, seg[a]);
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(seg[--b], R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
template< typename Monoid, typename F >
SegmentTree< Monoid, F > get_segment_tree(int N, const F& f, const Monoid& M1) {
return {N, f, M1};
}
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
auto seg = get_segment_tree(n, [](int a, int b){ return (gcd(a, b)); }, 0);
for(int i = 0; i < n; ++i){
seg.set(i, a[i]);
}
seg.build();
vector<long long> ans(1e6 + 1);
for (int i = 1; i <= 1e6; ++i) {
for (int j = i; j <= 1e6; j += i) {
ans[j] += i;
}
}
for(int i = 0; i < q; ++i){
int t, x, y;
cin >> t >> x >> y;
--x;
if(t == 1){
seg.update(x, y);
}else{
cout << ans[seg.query(x, y)] << '\n';
}
}
return (0);
}

ステータス

項目 データ
問題 1516 - 『公約数』総和企画
ユーザー名 ei1903
投稿日時 2021-11-17 21:16:03
言語 C++17
状態 Accepted
得点 5
ソースコード長 3529 Byte
最大実行時間 134 ms
最大メモリ使用量 22068 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 102 ms 11356 KB
1
in02.txt AC 69 ms 11152 KB
1
in03.txt AC 129 ms 11080 KB
1
in04.txt AC 102 ms 11240 KB
1
in05.txt AC 134 ms 11548 KB
1
in06.txt AC 74 ms 11560 KB
1
in07.txt AC 115 ms 11928 KB
1
in08.txt AC 109 ms 9684 KB
1
in09.txt AC 99 ms 10780 KB
1
in10.txt AC 74 ms 12012 KB
1
in11.txt AC 56 ms 10140 KB
1
in12.txt AC 73 ms 10064 KB
1
in13.txt AC 100 ms 11184 KB
1
in14.txt AC 76 ms 11472 KB
1
in15.txt AC 71 ms 12956 KB
1
in16.txt AC 64 ms 11800 KB
1
in17.txt AC 90 ms 10644 KB
1
in18.txt AC 65 ms 10756 KB
1
in19.txt AC 133 ms 14104 KB
1
in20.txt AC 133 ms 14404 KB
1
in21.txt AC 121 ms 16112 KB
1
in22.txt AC 125 ms 16796 KB
1
in23.txt AC 114 ms 17604 KB
1
in24.txt AC 109 ms 18548 KB
1
in25.txt AC 107 ms 19108 KB
1
in26.txt AC 111 ms 19924 KB
1
in27.txt AC 109 ms 20740 KB
1
in28.txt AC 126 ms 22068 KB
1
sample.txt AC 46 ms 19296 KB
1