## E - Guess the Sum Editorial by en_translator

This is similar to ABC349-D Divide Interval in that the allowed queries form a segment tree. The difference here is that we can do subtractions. For example, suppose that \(N=3,L=1\), and \(R=7\). If you split the segment in the same manner as ABC349-D, three queries are required: \(A_1,A_2+A_3\), and \(A_4+A_5+A_6+A_7\). On the other hand, in this problem we can ask \(A_0+A_1+A_2+A_3+A_4+A_5+A_6+A_7\) first, then \(A_0\), and finally subtract the second response from the first to obtain the answer.

In the following equations, the modular equivalence are modulo \(100\).

For integers \(x,y(0\leq x,y\leq 2^N)\), we define \(S(x,y)\) as follows:

\[ S(x,y)\equiv \begin{cases} 0\ (x=y) \\ \displaystyle\left( \sum_{i=x}^{y-1} A_i\right)\ (x<y)\\ -S(y,x)\ (x>y) \end{cases}\]

What we want is \(S(L,R+1)\), and what we can ask is \(S\left(2^ij,2^i(j+1)\right)\). Since \(S\left(2^i(j+1),2^ij\right)\equiv-S\left(2^ij,2^i(j+1)\right)\), we also assume that we can ask \(S\left(2^i(j+1),2^ij\right)\). If we know \(S(x,y)\) and \(S(y,z)\), we can obtain \(S(x,z)\) as \(S(x,y)+S(y,z)\).

Here, consider a graph \(G\) with \(2^N+1\) vertices labeled \(0,1,\dots,2^N\), with an edge between each pair \(x,y\) such that asking \(S(x,y)\) is allowed.

For two vertices \(x\) and \(y\) whose distance on \(G\) is \(2\), one can determine \(S(x,y)\) by asking twice, \(S(v_0,v_1)\) and \(S(v_1,v_2)\), where \(v_0(=x),v_1,v_2(=y)\) are the vertices on the shortest path from \(x\) to \(y\) on \(G\).

Likewise, for two vertices \(x\) and \(y\) whose distance on \(G\) is \(3\), one can determine \(S(x,y)\) with three questions, \(S(v_0,v_1)\), \(S(v_1,v_2)\), and \(S(v_2,v_3)\), where \(v_0(=x),v_1,v_2,v_3(=y)\) are the vertices on the shortest path from \(x\) to \(y\) on \(G\).

More generally, for two vertices \(x\) and \(y\) whose distance on \(G\) is \(d\), one can determine \(S(x,y)\) with \(d\) questions.

Therefore, it is sufficient to find (and reconstruct) the shortest path from \(L\) to \(R\) on the graph \(G\). Since graph \(G\) has \(2^N+1\) vertices and \(2^{N+1}-1\) edges, one can use BFS (Breadth-First Search) to find the shortest path in a total of \(O(2^N)\) time.

```
from collections import deque
N, L, R = map(int, input().split())
n = 1 << N
edge = [[] for i in range(n + 1)]
for i in range(N + 1):
for l in range(0, n, 1 << i):
r = l + (1 << i)
edge[l].append(r)
edge[r].append(l)
parent = [None] * (n + 1)
parent[R + 1] = -1
dq = deque([R + 1])
while dq:
v = dq.popleft()
for u in edge[v]:
if parent[u] == None:
parent[u] = v
dq.append(u)
ans = 0
now = L
while parent[now] != -1:
p = parent[now]
sgn = 1
l, r = now, p
if l > r:
sgn = -1
l, r = r, l
i = (r - l).bit_length() - 1
j = l >> i
print("?", i, j, flush=True)
T = int(input())
ans += sgn * T
now = p
print("!", ans % 100)
```

posted:

last update: