![]()
풀이 누적합과 투포인터를 이용한다. 왼쪽 포인터와 오른쪽 포인터를 설정하여 구간의 합을 계산한다. 구간의 합이 M과 같으면 경우의 수를 증가시키고 M보다 작으면 오른쪽 포인터를 증가시켜 구간을 확장하고 구간 합이 M보다 크면 왼쪽 포인터를 증가시켜 구간을 축소시킨다. 오른쪽 포인터가 끝에 도달할 때까지 반복한다. 시간복잡도 O(N) 코드 #include #include using namespace std; int main() { int N, M; cin >> N >> M; vector A(N); for (int i = 0; i > A[i]; } int count = 0; int left = 0; int right = 0; int sum = A[0]; while (right ..
https://www.acmicpc.net/problem/16713 16713번: Generic Queries 첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$) 둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$) 그 후, $Q$개의 줄에 걸 www.acmicpc.net 누적합(prefix sum)알고리즘을 사용해서 O(N)시간에 답을 구하는 것이 핵심인것 같습니다. 다만 더하기(+) 연산 대신 XOR(^) 연산을 사용해서 문제를 풀어야합니다. 전체적인 알고리즘 흐름은 "11659번: 구간 합 구하기4" 문제와 비슷합니다. 누적 XOR 배..
