1 sounds like the minimum value we can get. Why? Is it always true?

When n ≤ 2, we can do nothing. When n ≥ 3, since , n - 1 isn't a divisor of n, so we can choose it and get 1 as the result.

n = int(input())
	
if n == 2:
    print(2)
else:
	print(1)

You're given a permutation p of n elements. Each person i gives their item to p[i]. The process continues daily. For each person, compute the number of days it takes to get their own item back.

This is equivalent to finding the length of the cycle each element is part of

Can u check the constraints

For each element, follow the permutation until it loops back to the original position

def check(p, n):
    res = [0] * n
    for i in range(n):
        cnt = 1
        cur = p[i] - 1
        while cur != i:
            cur = p[cur] - 1
            cnt += 1
        res[i] = cnt
    return res

q = int(input())
for _ in range(q):
    n = int(input())
    p = list(map(int, input().split()))
    print(*check(p, n))

For each element, follow the permutation until it loops back to the original position

from collections import defaultdict, deque

q = int(input())
for _ in range(q):
    n = int(input())
    p = list(map(int, input().split()))
    graph = defaultdict(list)
    for i in range(1, n + 1):
        graph[i].append(p[i - 1])

    ans = []
    for i in range(1, n + 1):
        queue = deque([i])
        visited = {i}
        days = 0
        while queue:
            node = queue.popleft()
            for neighbour in graph[node]:
                if neighbour not in visited and neighbour != node:
                    visited.add(neighbour)
                    queue.append(neighbour)
                    days += 1
        ans.append(days + 1)
    print(*ans)

Can we see that every element belonging to the same cycle actually forms a group together?

To solve the problem efficiently, we can use the Disjoint Set Union (DSU) data structure, also known as Union-Find, which is ideal for managing groups of connected elements. The core idea is to treat each cycle in the permutation as a group and then track these groups as we process the permutation.

The DSU allows us to efficiently group elements together and later find the size of each group. For this problem, we will use path compression in the find operation to speed up future queries, and union by size to ensure we merge smaller groups into larger ones, which optimizes the union operation.

We start by initializing the DSU for each test case, where each element is its own parent. Then, for each element in the permutation, we union the element with the one it points to. After processing all elements, we can use the find operation to determine the root of each element's cycle and then count the size of each cycle by checking the size of the connected group it belongs to.

This approach ensures that we can efficiently handle the problem even with large inputs, as the time complexity for both union and find operations is nearly constant, due to the inverse Ackermann function, which grows extremely slowly. Thus, the solution is both time-efficient and space-efficient for large values of n.

Time Complexity: O(n * α(n)) per test case, where n is the number of elements and α(n) is the inverse Ackermann function. For practical input sizes, α(n) is very small, often treated as a constant.

Space Complexity: O(n) for storing the parent, rank (or size), and other DSU-related arrays.

import sys

input = sys.stdin.readline

# Input helpers
I = lambda: int(input())
ILT = lambda: list(map(int, input().split()))

class DSU:
    def __init__(self, n):
        self.rank = [0] * (n + 1)
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, node):
        if node == self.parent[node]:
            return node
        stack = []
        while node != self.parent[node]:
            stack.append(node)
            node = self.parent[node]
        for n in stack:
            self.parent[n] = node
        return node

    def Sunion(self, u, v):  # Union by size
        rep_u = self.find(u)
        rep_v = self.find(v)
        if rep_u == rep_v:
            return
        if self.size[rep_u] < self.size[rep_v]:
            self.parent[rep_u] = rep_v
            self.size[rep_v] += self.size[rep_u]
        else:
            self.parent[rep_v] = rep_u
            self.size[rep_u] += self.size[rep_v]

    def Runion(self, u, v):  # Union by rank
        rep_u = self.find(u)
        rep_v = self.find(v)
        if rep_u == rep_v:
            return
        if self.rank[rep_u] < self.rank[rep_v]:
            self.parent[rep_u] = rep_v
        elif self.rank[rep_v] < self.rank[rep_u]:
            self.parent[rep_v] = rep_u
        else:
            self.parent[rep_v] = rep_u
            self.rank[rep_u] += 1

def solve():
    n = int(input())
    p = list(map(int , input().split()))
    uf = DSU(n)
    for i in range(n):
        uf.Sunion(p[i], i + 1)
    print(*[uf.size[uf.find(i)] for i in range(1, n + 1)])

for _ in range(int(input())):
    solve()

Instead of simulating destruction from the beginning, try reversing the process. Imagine you start with an empty array, and at each step you restore one element.

When you restore an element, you want to join it with its neighbors (if they are already restored), to form a continuous segment. To track segments and their sums efficiently, you can use a structure that merges and finds connected components.

Use a disjoint set (also called union-find) to keep track of connected segments and their total sums. Each restored position is its own segment initially. Then, if neighboring positions are restored, you merge them and update the total.

Here's the idea:

• Process the array in reverse destruction order (i.e., imagine "restoring" the numbers).
• Keep track of which positions are active using a union-find structure.
• For each newly added number:
• Set its value.
• If neighbors are already restored, merge the segments.
• Update the maximum segment sum seen so far.
• Store the maximum sum after each restoration. At the end, reverse the answer to match the original destruction order.

This approach works in O(n * α(n)) where α is the inverse Ackermann function — effectively constant.

import sys

# Union-Find (Disjoint Set Union) with segment sum tracking
class Dsu:
    def __init__(self, size):
        self.parent = [i for i in range(size + 1)]  # parent[i] = leader of the set containing i
        self.size = [1 for i in range(size + 1)]    # size[i] = size of set with leader i
        self.total = [-1 for i in range(size + 1)]  # total[i] = sum of the segment with leader i

    def find(self, x):
        # Path compression to find leader
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Merge two segments
        px = self.find(x)
        py = self.find(y)

        if px != py:
            # Union by size (smaller into larger)
            if self.size[px] > self.size[py]:
                px, py = py, px
            self.parent[px] = py
            self.size[py] += self.size[px]
            self.total[py] += self.total[px]  # Update total segment sum

  
def solve():
    n = int(sys.stdin.readline().strip())
    nums = [0] + list(map(int, sys.stdin.readline().strip().split()))  # 1-indexed
    queries = list(map(int, sys.stdin.readline().strip().split()))     # destruction order

    dsu = Dsu(n)
    ans = [0]  # answer after 0 restorations
    maxi = 0   # current maximum segment sum

    # Process in reverse: simulate "restoring" elements
    for val in queries[::-1]:
        dsu.total[val] = nums[val]  # restore the value at position `val`

        # Try to join with the left neighbor
        if val - 1 > 0 and dsu.total[val - 1] > -1:
            dsu.union(val - 1, val)

        # Try to join with the right neighbor
        if val + 1 <= n and dsu.total[val + 1] > -1:
            dsu.union(val + 1, val)

        # Get the sum of the segment that includes this restored value
        cursum = dsu.total[dsu.find(val)]
        maxi = max(maxi, cursum)
        ans.append(maxi)  # save current max after this restoration

    # Remove the last dummy value and reverse to match destruction order
    ans.pop()
    for val in ans[::-1]:
        print(val)
    

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 \lt 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)