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="")

We can easily add a friend to the display system when that friend goes online. When there is a query to check if a friend can be displayed by the system, we need to remove friends with the lowest goodness values until the size of the online friends list is less than or equal to $$$k$$$. The answer will be $$$YES$$$ if the friend exists in the displayed system. If the friend is not currently in the display system, either because they were never added or because they were removed from the list, the answer will be $$$NO$$$.

Time Complexity: $$$(O(q * log(n)))$$$ where $$$q$$$ is number of queries and $$$n$$$ is number of friends Space Complexity: $$$O(n)$$$

from heapq import heappop, heappush
from collections import defaultdict

def main():
    n, k, q = map(int, input().split())
    friendship = list(map(int, input().split()))
    hashMap = defaultdict(int)
    heap = []

    for _ in range(q):
        type, friend = map(int, input().split())
        if type == 1:
            hashMap[friend] = 2
            heappush(heap, (friendship[friend - 1], friend))
        else:
            if hashMap[friend]:
                while len(heap) > k:
                    weight, f = heappop(heap)
                    hashMap[f] = 1 
            if hashMap[friend] == 2:
                print('YES') 
            else:
                print('NO')
    
if __name__ == '__main__':
    main()
 
 

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()

Consider an $$$N$$$-vertex directed graph where for each $$$i$$$ $$$(1 \leq i \leq M)$$$, there is an edge from vertex $$$a_i$$$ to vertex $$$b_i$$$. The goal is to find the lexicographically smallest sequence of topologically sorted vertices.

Topological sorting can be applied to the directed graph we have built. By choosing the vertex with the smallest index and indegree 0 at each step, we obtain the lexicographically smallest sequence $$$S$$$.

To choose the vertex with the smallest index and indegree, we can use a heap data structure.

import heapq

N, M = map(int, input().split())
indeg = [0] * N
out = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    indeg[b] += 1
    out[a].append(b)

heap = []
for i in range(N):
    if indeg[i] == 0:
        heapq.heappush(heap, i)

ans = []
while heap:
    i = heapq.heappop(heap)
    ans.append(i)
    for j in out[i]:
        indeg[j] -= 1
        if indeg[j] == 0:
        	heapq.heappush(heap, j)

if len(ans) != N:
    print(-1)
else:
    print(*[x + 1 for x in 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)