백준 13704 (C++) 수열과 쿼리 11

최초 업로드: 2025-11-20 16:02:17

최근 수정 시간: 2025-11-20 16:05:26

게시자: rlatjwls3333

카테고리: 백준

# [Platinum I] 수열과 쿼리 11

[문제 링크](https://www.acmicpc.net/problem/13704)

## 문제 설명

길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

## 입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)과 K (0 ≤ K ≤ 1,000,000)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 1,000,000)

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에는 쿼리 l, r이 한 줄에 하나씩 주어진다. (1 ≤ l ≤ r ≤ n)

## 출력

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

## 풀이
preSum[i]를 i까지의 A값을 모두 XOR한 값이라 하면, 오른쪽이나 왼쪽으로 늘어날 때는 cnt는 cur[preSum[i]]만큼 늘어나고, cur[preSum[i]^k]이 하나 늘어난다. 줄어들 때는 먼저 cur[preSum[i]^k]이 하나 감소하고, cnt가 cur[preSum[i]]만큼 감소한다. s ~ e 구간에 대한 답을 찾으려면 preSum[e]-preSum[s-1]이 구간 값을 모두 XOR한 값이기에 s-1 ~ e 구간을 고려해야 한다는 사실을 유의해야 하고, 개별 선택도 하나의 선택이기에 cur[k]에 1을 미리 넣어 놔야 한다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll sqrtN, a[100'001], cur[2'000'001];

struct element {
 int s, e, idx;
 bool operator<(const element el) const {
 if(s/sqrtN!=el.s/sqrtN) return s/sqrtN < el.s/sqrtN;
 return e < el.e;
 }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, k; cin >> n >> k;
 for(int i=1;i<=n;i++) {
 cin >> a[i];
 a[i]^=a[i-1];
 }
 sqrtN = sqrt(n);

int m; cin >> m;
 vector<element> v(m);
 for(int i=0;i<m;i++) {
 cin >> v[i].s >> v[i].e;
 v[i].idx=i;
 }
 sort(v.begin(), v.end());

vector<ll> res(m);
 cur[k]=1;
 ll cnt=0, l=0, r=0;
 for(auto [s, e, idx]:v) {
 while(l+1<s) {
 cur[k^a[l]]--;
 cnt -= cur[a[l++]];
 }
 while(s<=l) {
 cnt += cur[a[--l]];
 cur[k^a[l]]++;
 }
 while(r<e) {
 cnt += cur[a[++r]];
 cur[k^a[r]]++;
 }
 while(e<r) {
 cur[k^a[r]]--;
 cnt -= cur[a[r--]];
 }
 res[idx] = cnt;
 }
 for(ll e:res) cout << e << '\n';
}
```