17422번 - 지폐가 넘쳐흘러 서브태스크

💸 DJ욱제는 디제잉으로 큰 돈을 벌어서 FLEX 하고 있다. 💸

DJ욱제는 오늘 파티에서 FLEX 하려고 한다. DJ욱제는 각 W_i개의 지폐가 들어 있는 N개의 금고를 포화 이진 트리(노드가 2^k-1개인 이진 트리, k는 1 이상의 자연수) 형태로 연결했다. 가장 위에 있는 꼭대기 금고의 번호는 1이고, N번 금고의 좌우 자식 금고 번호는 각 2×N, 2×N+1이다. DJ욱제는 이 트리를 가지고 놀다가, 가장 많은 지폐가 들어 있는 금고를 털어서 FLEX 할 작정이다.

DJ욱제는 Q번의 놀이를 할 것이다. 매 놀이마다, 한 금고에 들어 있는 지폐 개수를 임의로 바꾸고 아래와 같이 행동한다.

1. 임의의 금고(지폐 개수를 바꾼 금고가 아니어도 됨)를 하나 선택해서, 그 금고를 루트 금고로 잡는다.
2. 1에서 선택한 루트 금고를 맨 위로 끌어 올리고, 나머지 금고들의 높이를 다시 맞춰서 루트 금고와의 거리가 같은 금고들이 같은 높이에 위치하도록 한다. 이때, 금고끼리의 연결은 끊어지거나 변하지 않는다.
3. 모든 금고의 문을 동시에 연다. 금고에 들어 있던 지폐들은 연결된 자식 금고들 중 어딘가로 떨어진다. 더 이상 떨어질 곳이 없다면, 그 금고에 쌓인다.
4. 지폐가 가장 많이 쌓인 금고를 확인하고, 그 금고의 지폐 개수를 센다.
5. 1번 과정을 실행하기 전으로 트리를 복원한다. 놀이에서 바꾼 지폐 개수는 그 다음 놀이에서도 계속 유지된다.

DJ욱제는 최대한 많은 돈을 FLEX 하고 싶지만, 똑같은 금고를 루트로 삼더라도 지폐가 어디로 어떻게 떨어지느냐에 따라서 금고에 쌓이는 지폐의 양이 달라질 수 있다. 그래서 DJ욱제는 온 우주의 힘을 믿고 간절히 기도하기로 했다.

DJ욱제와 함께, Q+1번에 걸쳐, 루트 금고를 잘 고르고 지폐들이 최적으로 잘 떨어졌을 때, 지폐가 가장 많이 쌓이는 금고에는 얼마만큼의 지폐가 쌓이게 되는지 알아보자!

첫째 줄에 금고의 개수 N이 주어진다. 양의 정수 k에 대해, N = 2^k-1이 항상 성립한다.

둘째 줄에 금고에 들어 있는 지폐의 개수 W_i가 1번 금고부터 순서대로 주어진다.

셋째 줄에 놀이의 횟수 Q가 주어진다.

이후 Q개의 줄에 걸쳐 i와 D_i가 주어진다. 이는 i번 금고의 지폐 개수를 D_i로 변경한다는 의미이다.

첫째 줄에 최초의 트리에서 하나의 금고에 쌓을 수 있는 지폐의 최대 개수를 출력한다.

이후 Q개의 줄에 걸쳐, i번째 놀이에서 하나의 금고에 쌓을 수 있는 지폐의 최대 개수를 출력한다.

• 1 ≤ N ≤ 262,143
• 0 ≤ W_i ≤ 100,000,000
• 0 ≤ Q ≤ 100,000
• 1 ≤ i ≤ N
• 0 ≤ D_i ≤ 100,000,000

이 서브태스크는 다음의 조건을 만족한다.

• N = 1 or 3
• 0 ≤ W_i ≤ 1,000
• Q = 0

이 서브태스크는 다음의 조건을 만족한다.

• 1 ≤ N ≤ 4,095
• 0 ≤ W_i ≤ 1,000
• Q = 0

이 서브태스크는 다음의 조건을 만족한다.

• Q = 0

이 서브태스크는 추가 제한 조건이 없다.