For this problem, the constraints allow us to implement it in $$$O(n)^2$$$ time, but let's try to do it in linear time complexity. We can have a variable for the final answer and iterate through the given string s. If the last character in our answer is a vowel and if $$$s_i$$$ is also a vowel, we can skip adding it to our answer; otherwise, we will add $$$s_i$$$ to our answer.

import sys
input = sys.stdin.readline

N = int(input())
word = input()

answer = []
vowels = {'a', 'e', 'i', 'o', 'u', 'y'}
for char in word:
    if answer and answer[-1] in vowels and char in vowels:
        continue
    answer.append(char)
print(*answer, sep="")

Can we get a better value for $$$z$$$?

Note that $$$z$$$ is masking itself. Therefore its value cannot increase larger than the initial value.

We can now conclude that to get a maximum value, we just need to apply the operation to each index once without changing $$$z$$$. Then take the maximum $$$a_i$$$.

This will tell us that we only actually applied the operation to the number that gives us the maximum value (just once).

t = int(input())
for _ in range(t):
    n, z = map(int, input().split())
    a = list(map(int, input().split()))

    max_val = 0
    for num in a:
        max_val = max(max_val, num | z)

    print(max_val)

To achieve the maximum $$$AND$$$ result, we set bits from the $$$30th$$$ bit down to the $$$0th$$$ bit for each number in the given array. However, the available operations $$$k$$$ may be less than the number of elements in the array $$$nums$$$. We first count how many operations we need for each bit position from $$$0$$$ to $$$30$$$ and store these counts in an array $$$needs$$$. Starting with the $$$30th$$$ bit (highest bit), we check if the operations required $$$needs[i]$$$ for setting that bit is within the available operations $$$k$$$. If it is less than or equal to $$$k$$$, we set that bit in the result $$$answer$$$ and subtract the required operations from $$$k$$$. This way, we prioritize setting higher bits in $$$answer$$$ first, as they have a greater impact on the value.

Time Complexity: $$$O(n)$$$

Space Complexity: $$$O(1)$$$

def main():
    for _ in range(int(input())):
        n, k = map(int, input().split())
        nums = list(map(int, input().split()))
        needs = [0] * 31

        for loc in range(31):
            for num in nums:
                if num & (1 << loc) == 0:
                    needs[loc] += 1
        
        max_val = 0

        for i in range(len(needs) - 1, -1, -1):
            if needs[i] <= k:
                max_val |= (1 << i)
                k -= needs[i]
        
        print(max_val)
    
if __name__ == '__main__':
    main()

Try calculating $$$f(l,r)$$$ bit by bit

Which condition has to hold true for all elements on a subsegment $$$[l,r]$$$, and for a certain bit, for that bit to be present in $$$f(l,r)$$$?

How can we check if that condition is true for a certain bit fast?

Try prefix sums.

Try binary search.

1. Calculating Prefix Sums of Bits:
   • We start by counting how many times each bit appears in the array up to a certain point. For example, how many 1s or 0s are there in the first few elements of the array.
   • We do this efficiently in $$$O(n \log(\text{max}(a)))$$$ time. Here, '$$$n$$$' is the length of the array, and '$$$\text{max}(a)$$$' is the maximum value in the array.
2. Understanding Bit Presence in a Range:
   • If the count of a particular bit (like the $$$j$$$-th bit) from index $$$l$$$ to index $$$r$$$ in the array is exactly the same as the length of that range $$$(r - l + 1)$$$, it means that bit appears in all the elements within that range.
3. Calculating $$$f(l,r)$$$:
   • Now, we want to find out for which bits this condition holds true within a certain range $$$[l, r]$$$ of the array.
   • We sum up the counts of all the bits where this condition holds true. This gives us the value of $$$f(l,r)$$$.
4. Solving Queries Efficiently:
   • For each query, given $$$l$$$ and $$$k$$$, we want to find the rightmost index $$$r$$$ such that $$$f(l,r)$$$ is greater than or equal to $$$k$$$.
   • We can use binary search to efficiently find $$$r$$$.
   • If $$$f(l,\text{mid})$$$ is greater than or equal to $$$k$$$, we move towards the right to find a larger $$$r$$$.
   • If not, we move towards the left to find a smaller $$$r$$$.
5. Overall Time Complexity:
   • This entire approach takes $$$O(Q \log(N) \log(\text{max}(a)))$$$ time to process all the queries, where $$$Q$$$ is the number of queries, $$$N$$$ is the length of the array, and $$$\text{max}(a)$$$ is the maximum value in the array.
   • For typical values, this works out to about $$$4 \times 10^7$$$ operations, which is pretty efficient.

So, by using this method, we efficiently handle queries about the presence of certain bits in specific ranges of the array.

t = int(input())
for _ in range(t):
    n = int(input()) 
    nums = list(map(int, input().split()))  
    q = int(input()) 

    arr = [0] * 32
    prefix = [arr]  # Initialize prefix array with zeros

    # Calculate prefix sums of bits
    for num in nums:
        arr = prefix[-1].copy()
        for i in range(32):
            # If the i-th bit is set in num, increment the corresponding count in arr
            if num & (1 << i) != 0:
                arr[i] += 1
        prefix.append(arr)

    # Function to find the bitwise AND of all numbers within a range
    def rangeAnd(l, r):
        ans = 0
        for i in range(32):
            bit_count = prefix[r][i] - prefix[l - 1][i] if l > 0 else prefix[r][i]
            if bit_count == (r - l + 1):
                ans |= (1 << i)
        return ans

    # Binary search to find the rightmost index satisfying the condition
    def bin_search(l, k):
        left = l
        right = n
        while left <= right:
            mid = (right + left) // 2
            if rangeAnd(l, mid) >= k:
                left = mid + 1
            else:
                right = mid - 1

        if right < l:
            return -1
        return right

    ans = []
    # Process queries
    for _ in range(q):
        l, k = map(int, input().split())
        ans.append(bin_search(l, k))

 
    print(*ans)

First solve a simplified version: suppose that in type $$$1$$$ queries, only a single character of the string s is inverted, i.e., $$$l=r$$$ in all type $$$1$$$ queries.

When we invert $$$s_i$$$, the XOR of all numbers from group $$$0$$$ and group $$$1$$$ change in the same way, regardless of whether this inversion was from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$.

We will store $$$2$$$ variables: $$$X_0,X_1$$$, which represent the XOR of all numbers from group $$$0$$$ and group $$$1$$$, respectively. When answering a query of type $$$2$$$, we will simply output either $$$X_0$$$ or $$$X_1$$$. Now we need to understand how to update $$$X_0$$$ and $$$X_1$$$ after receiving a query of type $$$1$$$.

Let's first solve a simplified version: suppose that in type $$$1$$$ queries, only a single character of the string s is inverted, i.e., $$$l=r$$$ in all type $$$1$$$ queries.

Let's see how $$$X_0$$$ and $$$X_1$$$ change after this query. If $$$s_i$$$ was $$$0$$$ and became $$$1$$$, then the number $$$a_i$$$ will be removed from group $$$0$$$. Since $$$XOR$$$ is its own inverse operation ($$$w⊕w=0$$$), we can do this with $$$X_0=X_0⊕a_i$$$. And in $$$X_1$$$, we need to add the number $$$a_i$$$, since now $$$s_i=1$$$. And we can do this with $$$X_1=X_1⊕a_i$$$.

The same thing happens if $$$s_i$$$ was $$$1$$$.

This is the key observation: when we invert $$$s_i$$$, $$$X_0$$$ and $$$X_1$$$ change in the same way, regardless of whether this inversion was from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$.

Therefore, to update $$$X_0$$$ and $$$X_1$$$ after a query of type $$$1$$$ with parameters $$$l,r,$$$ we need to do this: $$$X_0=X_0⊕(a_l⊕…⊕a_r)$$$, and the same for $$$X_1$$$.

To quickly find the XOR value on a subsegment of the array a, we can use a prefix XOR array. If $$$p_i=a_1⊕…a_i$$$, then: $$$a_l⊕…⊕a_r=p_r⊕p_{l−1}$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    s = sys.stdin.readline().strip()
    q = int(sys.stdin.readline().strip())

    pref = [0] * (n + 1)
    for i in range(1, n + 1):
        pref[i] = pref[i - 1] ^ a[i-1]

    x_0 = 0
    x_1 = 0
    for i in range(n):
        if s[i] == "0":
            x_0 ^= a[i]
        else:
            x_1 ^= a[i]

    ans = []
    for i in range(q):
        line = list(map(int, sys.stdin.readline().strip().split()))
        if line[0] == 2:
            if line[1]:
                ans.append(int(str(x_1)))
            else:
                ans.append(int(str(x_0)))
        else:
            l, r = line[1], line[2]
            seg = pref[r] ^ pref[l - 1]   
            x_0 ^= seg
            x_1 ^= seg
    print(*ans)

The formula given in this task looks difficult to calculate, so we can rewrite it:

$$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k) = \sum_{j=1}^n \sum_{i=1}^n (x_i \, \& \, x_j) \sum_{k=1}^n (x_j \, | \, x_k) = \sum_{j=1}^n \left[ \sum_{i=1}^n (x_i \, \& \, x_j) \right] \cdot \left[ \sum_{k=1}^n (x_j \, | \, x_k) \right]$$$

We fix the element $$$x_j$$$. Now the task is to calculate two sums $$$\sum_i (x_i \, \& \, x_j)$$$ and $$$\sum_k (x_j \, | \, x_k)$$$, and multiply them by each other.

Let's define function $$$f(x, c)$$$ as the value of $$$c$$$-th bit in $$$x$$$. For example $$$f(13, 1) = 0$$$, because $$$13 = 11\underline{0}1_2$$$, and $$$f(12, 2) = 1$$$, because $$$12 = 1\underline{1}00_2$$$. Additionally, define $$$M$$$ as the smallest integer such that $$$\forall_i \, x_i < 2^M$$$. Note that in this task $$$M \leq 60$$$.

We can rewrite our sums using function $$$f$$$:

$$$\sum_i (x_i \, \& \, x_j) = \sum_{c = 0}^{M} 2^c \sum_i f(x_i, c) \cdot f(x_j, c) = \sum_{c = 0}^{M} 2^c f(x_j, c) \sum_i f(x_i, c)$$$

$$$\sum_k (x_j \, | \, x_k) = \sum_{c = 0}^{M} 2^c \sum_k 1 - (1 - f(x_j, c)) \cdot (1 - f(x_k, c)) = \sum_{c = 0}^{M} 2^c \left[ n - (1 - f(x_j, c)) \sum_k (1 - f(x_k, c)) \right]$$$

In other words, we just split elements $$$x_i$$$, $$$x_j$$$, $$$x_k$$$ into the powers of two.

If we memorize the values of $$$\sum_i f(x_i, c)$$$, for each $$$c \in {0, 1, \ldots, M }$$$, then we can calculate the desired sums in $$$\mathcal{O}(M)$$$ for fixed $$$x_j$$$ using the above equations.

So the final solution is to iterate over all elements in the array and fix them as $$$x_j$$$, and sum all of the results obtained. Complexity is $$$\mathcal{O}(nM) = \mathcal{O}(n \log \max_i(x_i))$$$

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())

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

    MOD = 1000_000_007
    bit_counts = [0]*60
    for xi in x:
        for i in range(60):
            if xi&(1<<i):
                bit_counts[i] += 1
    ans = 0
    for xi in x:
        tot_or = tot_and = 0
        for i in range(60):
            if xi&(1<<i):
                tot_or += (1<<i)%MOD*N
                tot_or %= MOD
                tot_and += (1<<i)%MOD*bit_counts[i]
                tot_and %= MOD
            else:
                tot_or += (1<<i)%MOD*bit_counts[i]
                tot_or %= MOD
        ans += tot_or*tot_and
        ans %= MOD

    print(ans)