창하의 수열 뒤집기 이야기

시간 제한1초메모리 제한1024 MB

요약
길이 2^k인 수열 A와 -1, 0, 1로 이루어진 B가 주어지고, 각 B_i가 정해진 구간 뒤집기 시행 여부를 결정할 때, 갱신마다 얻을 수 있는 합의 최댓값을 구한다.
난이도

어려움10점 중 9점

유형
분할 정복, 트리, 동적 계획법, 비트 연산
정답자
아직 제출이 없습니다

문제

길이 N$$(N=2^k)인 수열 AA와 길이 N−1N-1인 수열 BB가 주어진다. B_1,B_2,⋯ ,B_N−1B\_1, B\_2, \cdots, B\_{N-1}의 값은 −1-1, 00, 11 중 하나이다. 연산 X_iX\_i를 다음과 같이 정의하자.

  • 연산 X_iX\_i: 수열 AA의 (2i+1)2k−⌊log⁡_2i⌋−1−2k+1(2i+1)2^{k-\lfloor\log\_2{i}\rfloor-1}-2^k+1번째부터 (i+1)2k−⌊log⁡_2i⌋−2k(i+1)2^{k-\lfloor\log\_2{i}\rfloor}-2^k번째 까지의 모든 원소에 −1-1을 곱한다.

창하는 ii에 11 이상 NN 이하의 정수를 오름차순으로 차례로 대입하며 아래 절차를 총 NN번 반복한다.

  • B_i=1B\_i=1이면, 연산 X_iX\_i를 시행한다.
  • B_i=0B\_i=0이면, 아무것도 하지 않는다.
  • B_i=−1B\_i=-1이면, 연산 X_iX\_i를 시행하거나 아무것도 하지 않는다.

창하는 시행이 끝났을 때 AA의 모든 원소들의 합의 최댓값을 알고 싶다. 하지만 AA와 BB는 총 QQ번 수정되며, 초기 상태와 각 수정 이후의 모든 AA와 BB에 대해 뒤집기 시행 후 ∑_i=1NA_i\sum\_{i=1}^{N}{A\_i}이 가질 수 있는 최댓값을 구해야 한다. 각 수정은 이후의 수정에도 영향을 미치며, 실제로 뒤집기를 시행하지는 않는다. 머리가 아픈 창하를 도와주자!

입력

첫 번째 줄에 정수 k$$(1\le k \le 18)가 주어진다.

두 번째 줄에 2k2^k개의 정수 A_1,A_2,⋯ ,A_2kA\_1, A\_2, \cdots, A\_{2^k}가 공백으로 구분되어 주어진다. (−109≤A_i≤109)(-10^9\le A\_i \le 10^9)

세 번째 줄에 2k−12^k-1개의 정수 B_1,B_2,⋯ ,B_2k−1B\_1, B\_2, \cdots, B\_{2^k-1}이 공백으로 구분되어 주어진다. (−1≤B_i≤1)(-1\le B\_i \le 1)

네 번째 줄에 정수 Q$$(1\le Q \le 10^5)가 주어진다.

다음 QQ개의 줄에 쿼리들의 정보가 주어지며, 각 줄에는 문자 cc, 두 개의 정수 ii, vv가 공백으로 구분되어 주어진다. (c \in \\{A,,B\\})

  • c=c= A인 경우 A_iA\_i의 값을 vv로 변경하는 것을 의미한다. (1≤i≤N;(1\le i \le N; −109≤v≤109)-10^9 \le v \le 10^9)
  • c=c= B인 경우 B_iB\_i의 값을 vv로 변경하는 것을 의미한다. (1≤i≤N−1;(1\le i \le N-1; −1≤v≤1)-1 \le v \le 1)

출력

첫 번째 줄에 수정 전 초기 상태의 AA와 BB에서 시행이 끝났을 때 가능한 ∑_i=1NA_i\sum\_{i=1}^{N}{A\_i}의 최댓값을 출력한다.

다음 QQ개의 줄 중 ii번째 줄에 ii번째까지 수정을 거친 수열 AA와 BB에서 시행이 끝났을 때 가능한 ∑_i=1NA_i\sum\_{i=1}^{N}{A\_i}의 최댓값을 출력한다.

힌트

⌊x⌋\lfloor x \rfloor는 xx를 넘지 않는 최대 정수를 의미한다.

예제1

  1. 예제 1

    입력
    2
3 -2 -4 5
1 1 0
3
A 2 -4
B 2 -1
B 1 -1
    예상 출력
    4
6
6
8