Let's sort the array in nonincreasing order. Now the answer is some of the first containers. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.

Complexity: $$$\mathcal{O}(nlogn)$$$.

n = int(input())
m = int(input())
flash = []
for _ in range(n):
    val = int(input())
    flash.append(val)
flash.sort(reverse=True)
cur = 0
for i in range(n):
    cur += flash[i]
    if cur >= m:
        print(i + 1)
        break

Note that for each question, the resulting array is

So, the sum of the elements of the new array after each question is

We can compute $$$a_1+⋯+a_{l−1}$$$ and $$$a_{r+1}+⋯+a_n$$$ in $$$\mathcal{O}(1)$$$ time by precomputing the sum of all prefixes and suffixes, or alternatively by using the prefix sums technique. So we can find the sum each time in $$$\mathcal{O}(1)$$$ per question, and just check if it's odd or not. The time complexity is $$$\mathcal{O}(n+q)$$$.

from itertools import accumulate
from sys import stdin


# Fast input for python. Note that it gives you the input with the newline character, '\n'
# This may cause a problem on string problems. In that case, use stdin.readline()[:-1] to strip the last character('\n')
def input(): return stdin.readline()


T = int(input())
for _ in range(T):
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))

    pref_sum = list(accumulate(a, initial=0))

    for __ in range(Q):
        l, r, k = map(int, input().split())
        left_sum = pref_sum[l - 1]
        right_sum = pref_sum[-1] - pref_sum[r]
        middle_sum = k*(r - l + 1)
        total_sum = left_sum + middle_sum + right_sum

        if total_sum%2 == 1:
            print("YES")
        else:
            print("NO")  

First, we need to determine how many times each operation will be performed. For instance, if our query is $$$1, 3$$$, and $$$2, 5$$$ then $$$2$$$ and $$$3$$$ will be done twice since they fall within two ranges, while the rest will be done once. To calculate this, we can use a prefix sum with range updates.

Next, for each operation $$$l, r, d, and$$$ $$$v$$$ (where $$$v$$$ represents the number of times it will be performed), we'll increment all elements from $$$l$$$ to $$$r$$$ inclusive by $$$d*v$$$. This can also be efficiently computed using a prefix sum with range updates.

prefix sum with range updates: Let's think about a somewhat easier problem first. What if we were asked to add a constant value to the suffix of the array starting at index l, for multiple queries? Instead of updating the whole suffix for each query, we can only increment the first index of the suffix for each query, $$$i.e a[l]+=k$$$. Then after all queries, we take the prefix sum of the whole array. This will "propagate" our increments till the end of the array and thus our task of updating the whole suffix is accomplished at the end, after taking prefix sums. Now, what about updating the range $$$[l…r]$$$? Can you decompose this range update as $2 suffix updates? It can be decomposed as such:

if you need to increment the range $$$[l…r]$$$ by $$$k$$$, you can increment the suffix starting at index $$$l$$$ by $$$k$$$ and decrement the suffix starting at index $$$r+1$$$ by $$$k$$$, i.e perform the operations $$$a[l]+=k$$$ and $$$a[r+1]−=k$$$ for each query and then take the prefix sum of the array as before.

A visual summary:

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
 
op = []
for _ in range(m):
    op.append(list(map(int, input().split())))
    
q = [0]*(m+1)
for _ in range(k):
    l, r = (map(int, input().split()))
    q[l-1] += 1
    q[r] -= 1
    
for i in range(m-1):
    q[i+1] += q[i]
 
update = [0]*(n+1)
for query in range(m):
    l,r,d = op[query]
    update[l - 1] += d*q[query]
    update[r] -= d*q[query]
for i in range(n-1):
    update[i+1] += update[i]
for i in range(n):
    a[i] += update[i]
print(*a)	

There is always one sheep that shouldn't move.

Let's denote by k the number of sheep in the string, and by $$$x_1,x_2,…,x_k$$$ $$$(1≤x_1<x_2<…<x_k≤n)$$$ their positions in the string. Note that in the optimal solution the sheep with the number $$$m=⌈n/2⌉$$$ will not make moves. This can be proved by considering the optimal solution in which the sheep with the number m makes at least one move. if it moves to the right all sheep that are to the left of $$$x_m$$$( $$$x_1,x_2,…,x_{m-1}$$$) will move by one to the right but not all the sheep that are on the left side of $$$x_m$$$( $$$x_{m+1},x{m+2},…,x_k$$$) will decrease their movement by one and same thing if the $$$m-th$$$ sheep move to the left. So we can conclude that this solution is not optimal. Consider sheep with numbers from i=1 to n

Then the final position of the $$$i-th$$$ sheep will be $$$x_m−m+i$$$, and the answer will be $$$\sum\limits_{k = 0}^n |xi−(xm−m+i)|$$$, since all the sheep have to move from $$$x_i$$$ to $$$x_m-m+i$$$.

testcases = int(input())
for _ in range(testcases)
    n = int(input())
    s = input().strip()
    cnt = s.count('*') # total count of sheeps
    pos = -1 # hold the position of the mth sheep
    cur = -1 
    for i in range(n):
        if s[i] == '*':
            cur += 1
            if cur == cnt // 2:
                pos = i

    ans = 0
    # pos -> xm cnt//2-> and i =-> 0
    cur = pos - cnt // 2
    for i in range(n):
        if s[i] == '*':
            ans += abs(cur - i)
            cur += 1

    print(ans)

Let the sum of elements from the beginning be $$$p_i$$$. $$$[l,r]$$$ is bad if the sum of all the elements between that range equals $$$r - l + 1$$$. so $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$.

Rewrite the formula $$$pr−pl + 1 = r−l + 1$$$.

Let's precalculate the array $$$p$$$, where $$$pi=\sum\limits_{j = 0}^{i - 1} a_j$$$(so $$$p_x$$$ is the sum of the first $$$x$$$ elements of $$$a$$$). Then subarray $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$, so $$$pr−r=pl−l$$$.

Thus, we have to group all prefixes by value $$$pi−i$$$ for $$$i$$$ from $$$0$$$ to $$$n$$$. And if x indexes have a prefix with the same value of $$$pi−i$$$ then we have to add $$$x(x−1)/2$$$ to the answer.

from collections import defaultdict
testcases = int(input())
for _ in range(testcases):
    n = int(input())
    a = input()
    d = defaultdict(int)
    d[0] = 1
    res, s = 0, 0
    
    for i in range(n):
        s += int(a[i])
        x = s - i - 1
        d[x] += 1
        
        res += d[x] - 1
        
    print(res)