Сигма-запити#13037

Сигма-запити (Розбір)

Автор задачі: & Hasan Saleh (MathModel)

Підготував: & Hasan Saleh (MathModel)

Редагував: & Hasan Saleh (MathModel)

Розв'язок

Випадок $- 1$ ніколи не трапляється, оскільки $a_{i} \geq 1$ a_i \ge 1, префіксні суми $b$ строго зростають і необмежені.

Нехай $S = i = 1 \sum n a_{i}$ S=\sum\limits_{i=1}^{n} a_i та $P_{r} = i = 1 \sum r a_{i}$ P_r=\sum\limits_{i=1}^{r} a_i, тоді записавши $k = m \cdot n + r$ k=m \cdot n+r з $0 \leq r \leq n$ 0 \le r \le n отримуємо

i = 1 \sum k b_{i} = m \cdot S + P_{r}

\sum\limits_{i=1}^{k} b_i=m \cdot S+P_r

Отже, нам потрібно лише обрати кількість повних копій $m$ , а потім завершити всередині ще однієї копії. Візьмемо

m = ⌊ \frac{x - 1}{S} ⌋

m=\left\lfloor \frac{x-1}{S} \right\rfloor

що є найбільшою кількістю копій, для якої $m \cdot S < x$ m \cdot S < x, і жодне менше значення не підходить, оскільки з $m^{'} < m$ m' < m та $r < n$ r<n випливає

m^{'} \cdot S + P_{r} < (m^{'} + 1) \cdot S \leq m \cdot S < x

m' \cdot S+P_r < (m'+1) \cdot S \le m \cdot S < x

Залишається $y = x - m \cdot S$ y=x-m \cdot S з $1 \leq y \leq S$ 1 \le y \le S, і оскільки $P$ строго зростає, ми виконуємо бінарний пошук мінімального $r$ , для якого $P_{r} \geq y$ P_r \ge y, що існує, оскільки $P_{n} = S \geq y$ P_n=S \ge y. Відповідь —

k = m \cdot n + r

k=m \cdot n+r

Зауважте, що $r = n$ r=n допустиме і просто означає, що відповідь припадає на кінець копії.

Складність становить $O (n + q lo g n)$ O(n+q \log n).

def solve():
    n,q=map(int,input().split())
    a=list(map(int,input().split()))
    x=list(map(int,input().split()))
    pre=[0]*(n+1)
    for i in range(1,n+1):
        pre[i]=pre[i-1]+a[i-1]
    total=pre[n]
    res=[]
    for v in x:
        m=(v-1)//total
        y=v-m*total
        lo,hi=1,n
        while lo<hi:
            mid=(lo+hi)//2
            if pre[mid]>=y:
                hi=mid
            else:
                lo=mid+1
        res.append(m*n+lo)
    print(*res)
for _ in range(int(input())):
    solve()

Python