이상한 십진법 XOR

한 자리 숫자 $d$의 색을 빨강부터 차례대로 $0,1,2,3,4$로 번호 매기고 상태를 $0,1$로 나타내자. 다음 대응 $f$를 사용한다.

$$(f(0),f(1),\cdots,f(9))=(0,5,6,1,2,7,8,3,4,9).$$

$f(d)$는 다음 두 조건을 만족하는 $0$ 이상 $9$ 이하의 유일한 정수이다.

• $f(d)\bmod 5$는 $d$의 색 번호이다.
• $f(d)\bmod 2$는 $d$의 상태이다.

색의 합성은 색 번호의 덧셈 modulo $5$이고, 상태의 XOR은 덧셈 modulo $2$와 같다. 중국인의 나머지 정리에 의해

$$f(x\diamond y)\equiv f(x)+f(y)\pmod{10}$$

이 성립한다.

$A_i$의 $10^j$ 자리 숫자를 $d_j(A_i)$라고 하자. 자리별 누적합을

$$S_i^j=\sum_{k=1}^{i} f(d_j(A_k))\pmod{10},\qquad S_0^j=0$$

으로 정의한다. 그러면 구간 $[l,r]$의 $10^j$ 자리 결과가 $0$인 것과 $S_{l-1}^j=S_r^j$인 것은 동치이다.

전체 결과가 $0$이려면 모든 십진 자리에서 동시에 이 조건을 만족해야 한다. $0\le A_i\le10^{18}$이므로 필요한 자리는 $j=0,1,\cdots,18$의 $19$개뿐이다. 따라서

$$S_i=(S_i^0,S_i^1,\cdots,S_i^{18})$$

라고 두면, 구간 $[l,r]$의 이상한 십진법 XOR가 $0$인 것과 $S_{l-1}=S_r$인 것은 동치이다.

서브태스크 1

$A_i\le9$이면 일의 자리만 0이 아닐 수 있다. 따라서 $S_i$는 사실상 modulo $10$ 값 하나뿐이다. 각 값 $0,1,\cdots,9$에 대해 누적 등장 횟수를 저장하면, 쿼리 $[L,R]$에서는 접두사 위치 $L-1,L,\cdots,R$에 각 값이 몇 번 등장하는지 $O(1)$에 구할 수 있다. 어떤 값이 $c$번 등장하면 같은 값을 고르는 위치 쌍은 $\binom{c}{2}$개이므로 한 쿼리를 $O(10)$에 처리할 수 있다.

시간 복잡도는 $O(N+10Q)$이고 공간 복잡도는 $O(10N)$이다.

전체 제약

이제 $S_i$는 길이 $19$인 벡터이고 가능한 값의 전체 공간은 너무 크다. 하지만 실제로 등장하는 벡터는 $S_0,S_1,\cdots,S_N$뿐이다. 이 벡터들을 사전순으로 정렬하여 같은 벡터에 같은 정수 ID를 부여한다.

그러면 각 쿼리 $[L,R]$은 접두사 위치 구간 $[L-1,R]$ 안에서 값이 같은 서로 다른 두 위치의 쌍의 개수를 묻는 문제가 된다.

이를 Mo's algorithm으로 오프라인 처리한다. 현재 구간에 ID $v$가 $c$개 들어 있을 때 새 원소 $v$를 추가하면 답이 $c$ 증가한다. 원소 $v$를 제거할 때는 먼저 개수를 하나 줄인 뒤 남은 개수만큼 답을 감소시키면 된다.

벡터 생성은 $O(19N)$, 좌표 압축은 $O(19N\log N)$, Mo's algorithm은 $O((N+Q)\sqrt N)$에 동작한다. 따라서 전체 시간 복잡도는

$$O(19N\log N+(N+Q)\sqrt N)$$

이고 공간 복잡도는 $O(19N+Q)$이다.

Solution written by GPT5.6