Alakazam
시간 제한2초메모리 제한512 MB
배열에서 구간을 무작위로 섞는 연산이 여러 번 주어질 때, 특정 위치에 있는 값의 기댓값을 구하는 문제입니다.
문제
안녕하세요, 포켓몬 트레이너 여러분! 당신도 사파리에 왔군요? 이곳에 와 주셔서 반갑습니다. Alakazam 군락을 발견한 사람이 바로 당신입니다!
군락은 n마리의 Alakazam으로 이루어져 있습니다. 각 개체는 초능력를 증폭시키는 숟가락을 여러 개 들고 있습니다. Alakazam들은 초능력 훈련을 하기 위해 줄을 섰습니다. 평범한 훈련이 아닙니다. 바로 순간이동 훈련입니다!
훈련은 여러 번의 집단 순간이동으로 구성됩니다. 각 순간이동에서 연속한 Alakazam 무리가 사라졌다가 이전과 같은 위치에 완전히 무작위한 순서로 다시 나타납니다.
훈련 직전에 당신은 각 Alakazam이 들고 있는 숟가락의 개수를 세었습니다. 하지만 훈련이 시작된 뒤에는 너무 멀리 있어서 숟가락을 셀 수 없었고, 순간이동만 지켜보았습니다. 관찰을 바탕으로, 훈련이 진행되는 동안 줄의 특정 위치에 있는 Alakazam이 숟가락을 몇 개 들고 있는지 예측할 수 있습니까? 과정이 무작위하므로 우리는 숟가락 개수의 기댓값만 묻습니다.
입력
첫째 줄에 두 정수 n, q (1 ≤ n ≤ 250 000, 1 ≤ q ≤ 250 000)가 주어집니다. n은 줄에 있는 Alakazam의 수이고 q는 훈련 중의 행동 수입니다. 다음 줄에 n개의 정수 a1, a2, . . . , an (1 ≤ ai ≤ 106)이 주어집니다. ai는 줄의 각 개체가 들고 있는 숟가락의 개수입니다.
다음 q개 줄은 각각 하나의 행동을 나타내며, 다음 형식 중 하나입니다.
- shuffle l r (1 ≤ l ≤ r ≤ n): l번째부터 r번째 개체까지(양 끝 포함)의 Alakazam 무리가 순간이동하여 무작위 순서로 다시 나타납니다.
- get i (1 ≤ i ≤ n): 줄의 i번째 Alakazam이 들고 있는 숟가락 개수의 기댓값을 예측해야 합니다.
파일에는 get 질의가 적어도 하나 있습니다.
출력
각 get 질의마다 지정된 Alakazam이 들고 있는 숟가락 개수의 기댓값을 나타내는 십진수를 한 줄에 하나씩 출력합니다.
답의 절대 오차 또는 상대 오차가 10-9를 넘지 않으면 정답으로 인정됩니다.
힌트
순간이동 전에 Alakazam은 숟가락을 1개, 2개, 3개 들고 있습니다:
첫 번째 순간이동 뒤에는 두 순열 (1, 2, 3)과 (2, 1, 3)이 같은 확률로 나타납니다. 한편 두 순간이동이 모두 끝난 뒤에는 다음 순열들이 같은 확률로 나타납니다: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1).