문제
n개의 수가 들어있는 a1 ~ an 수열이 주어진다.
당신은 2종류의 명령을 m번 처리해야 한다.
Q l r k : ai~ar 구간에서 k개를 제외하여 만들 수 있는 모든 조합의 GCD를 구한 뒤 그 값들의 LCM 출력
U j x : aj를 x로 변경
입력
첫 줄에 수열의 길이 n과 명령의 수 m이 주어진다.
다음 줄에 a1 ~ an 수열이 주어진다.
그 다음 m줄에 걸쳐 명령이 주어진다.
[제약조건]
1 <= n <= 105, 1 <= ai <= 106
1 <= m <= 105
1 <= j <= n, 1 <= x <= 106
1 <= l, 0 <= k <= 2, l+k <= r <= n
출력
명령이 들어온 순서대로 Q 명령에 대한 답을 각 줄에 출력한다.
예제
5 10
12 10 16 28 15
Q 1 3 1
Q 3 4 0
Q 2 2 0
Q 2 5 2
U 3 21
Q 1 3 1
Q 2 4 1
Q 3 5 1
Q 4 4 0
Q 2 5 2
4
4
10
20
6
14
21
28
210
예제에서 마지막 Q 2 5 2 과정은 아래 그림과 같다.
태그
출처
ICPC 2020 Asia Yokohama Regional H
로그인해야 코드를 작성할 수 있어요.