The general form of the sequence

Note that we're considering the operations when $$$m_1 \le m_2 \le m_3$$$.

Consider the case where $$$n$$$ is even:

The number of operations is the length of the sequence $$${2,4,6,\ldots, 2(\frac{n}{2}-1)}$$$ which is $$$\frac{n}{2}-1$$$.

Consider the case where $$$n$$$ is odd:

The number of operations is the length of the sequence $$${1,3,5,7,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$$$

By the representation of odd numbers we've $$${2(0)+1,2(1)1+,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$$$ , which is equivalent to the length of $$${0,1,2,\ldots, \frac{n-1}{2}-1}$$$ which gives the length of $$$\frac{n-1}{2}$$$.

Both cases are equivalent to the close form

Complexity $$$\mathcal{O}(1)$$$.

from math import *

def solve():
    n=int(input())
    print((n-1)//2)

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

It's possible to use fair split that's we use $$$\lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor + n \bmod 3$$$ and keep simulating with $$$n=m_3$$$ on steps except the first step until you reach $$$m_2 \le 2$$$.

Complexity $$$\mathcal{O}(\log_3(n))$$$

from math import *

def solve():
    n=int(input())
    a,b,c=n//3,n//3,n//3+(n%3)
    ans=0
    while(n>2):
        ans+=n//3
        n=n//3+(n%3)
    print(ans)

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

Great

Good

Neutral

Bad

Didn't Solve

If you've one $$$\color{blue}{\mathtt{B}}$$$ in string $$$s$$$ , then you'll have to do operations in $$$\mathcal{O}(n\log_2(A))$$$ which is $$$\sim \mathcal{O}(20 \cdot 30)$$$ which is fine for $$$n \le 20$$$ and $$$\sum q \le 10^4$$$ , at worst case this is roughly $$$\mathcal{O}(6 \cdot 10^5)$$$ which is safe.

If we've a string $$$s$$$ that's all $$$\color{red}{\mathtt{A}}$$$ i.e. :

then answer is simply for each $$$a_i$$$ is $$$a_i$$$ itself because we cannot do anything except just subtracting by $$$1$$$ many times ; otherwise the complexity becomes $$$\mathcal{O}(10^9q)$$$ for such cases which is slow.

Complexity $$$\mathcal{O}(nq \log_2(10^9))$$$.

def solve():
    n,q=map(int,input().split())
    s=input().strip()
    a=list(map(int,input().split()))
    A,B=s.count('A'),s.count('B')
    for i in range(q):
        if(B==0):
            print(a[i])
        else:
            ans=0
            while(a[i]):
                for j in s:
                    if(a[i]==0):break
                    ans+=1
                    if(j=='A'):a[i]-=1
                    else: a[i]//=2
            print(ans)

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

Observation : The consuming part of processing the operations where a segment of $$$\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$$$ because we're processing one by one which is inefficient and answering query will take $$$\mathcal{O}(nq \log_2(10^9))$$$ , why ? , because processing $$$\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$$$ operation-by-operation is slow , for example consider the sequence $$$\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}} \color{blue}{\mathtt{B}}}_{}$$$

This case will take $$$\mathcal{O}(nq \log_2(10^9))$$$ at worst case , which is inefficient.

A good way to optimize is by compress the blocks of same type of operations as $$$(\mathrm{type},\mathrm{count})$$$ that way all long blocks of $$$\color{red}{\mathtt{A}}$$$ will be performed much faster , For blocks of $$$\color{blue}{\mathtt{B}}$$$ it's already fast to process them in order because of $$$\mathcal{O}(\log_2(a))$$$ and it reduces $$$a$$$ to $$$0$$$ in $$$\mathcal{O}(\log_2(10^9)) \sim 30$$$ at most , However compressing the operations is still better to compose the operations.

That's we're going to process at most $$$\sim 60$$$ blocks , because if we started with $$$\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\ldots $$$ assuming $$$a=10^9$$$ , which is the worst case of the algorithm.

Now after composing the blocks as $$$(\mathrm{type},\mathrm{count})$$$ , you should iterate through them :

• If $$$s_i=\color{red}{\mathtt{A}}$$$ then we perform $$$a_i=a_i-\min(\mathrm{count},a_i)$$$
• If $$$s_i=\color{blue}{\mathtt{B}}$$$ then we perform $$$\displaystyle a_i=\left \lfloor \frac{a_i}{\displaystyle 2^{\min(\text{count},\lceil \log_2(n) \rceil)}} \right \rfloor$$$

make sure to update number of operations accordingly.

Complexity $$$\sim \mathcal{O}(n+q \log^2(10^9))$$$.

def solve():
    n,q=map(int,input().split())
    s=input()
    a=list(map(int,input().split()))
    A=s.count('A')
    B=s.count('B')
    last=s[0]
    seq=[] 
    cur=1
    for i in range(1,n):
        if(s[i]==last): cur+=1
        else:
            seq.append([last,cur])
            cur=1
            last=s[i]
    if(cur!=0): seq.append([last,cur])
    if(B==0):
        for i in a: print(i)
    else:
        for i in range(q):
            ans=0
            while(a[i]>0):
                for j in seq:
                    if(a[i]==0): break
                    if(j[0]=='A'):
                        mn=min(j[1],a[i])
                        ans+=mn
                        a[i]-=mn
                    else:
                        if a[i]==0: break
                        x=a[i]
                        p=0
                        while(x):
                            x//=2
                            p+=1
                        mn=min(p,j[1])
                        ans+=mn
                        a[i]//=(2**mn)
            print(ans)

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

Great

Good

Neutral

Bad

Didn't Solve

We want the maximum gcd $$$g$$$ achievable after $$$\le k$$$ erases and any splits.

For a fixed $$$g$$$, the elements that won’t consume an erase are:

• all multiples of $$$g$$$ (already good), and
• any $$$x\ge 4g$$$ (can be made good via one split using the construction in hint 3).

Thus, the only "bad" numbers (that would have to be erased) are those with $$$x\lt 4g$$$ that are not multiples of $$$g$$$. Therefore $$$g$$$ is good if

Since $$$1\le a_i\le n$$$, precompute a frequency array and prefix sums $$$p[v]=\sum_{u\le v}f[u]$$$. Then

Iterate through $$$g=1,2,3,\ldots ,n$$$ and keep the largest good $$$g$$$.

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

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
  int n,k;cin>>n>>k;
  vector<int>a(n),mp(n+1),p(n+1);
  for(auto &i:a){
     cin>>i;
     mp[i]++;
  }
  for(int i=1;i<=n;i++){
      p[i]=p[i-1]+mp[i];
  }
  int ans=1;
  for(int g=1;g<=n;g++){
    int t=min(n,4*g-1);
    int good=n-p[t];
    if(g<=n)good+=mp[g];
    if(2*g<=n)good+=mp[2*g];
    if(3*g<=n)good+=mp[3*g];
    if(good>=n-k)ans=g;
  }
  cout<<ans<<"\n";
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;cin>>t;
  while(t--)solve();
}

Great

Good

Neutral

Bad

Didn't Solve

Recall from Hint 2 that $$$\text{bit}_k(i)$$$ is defined as $$$k$$$-th bit of the integer $$$i$$$. A naive solution using $$$n\log_2 n$$$ queries is as follows:

• Compute $$$\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$$$ for all $$$k=0,1,\ldots,\lfloor\log_2 n\rfloor$$$.

  • $$$\text{bit}_k(p_i)$$$ can be computed with a single query $$$p_i \ \mathtt{AND} \ 2^k$$$ ($$$1\le i\le n - 1$$$).

• If $$$\text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) = \text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$$$, it means that the $$$k$$$-th bit of $$$p_n$$$ is zero. Otherwise, it is one.

  • This works due to the fact that $$$\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1}) = \text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) - \text{bit}_k(p_n)$$$.

To optimise this, we will half the search space after each step. Starting from $$$k = 0$$$, we still use $$$n - 1$$$ queries to calculate $$$\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$$$. After using this to determine the value of the $$$0$$$-th bit of $$$p_n$$$, we can discard all $$$p_i$$$ that has a different $$$0$$$-th bit from $$$p_n$$$.

More formally, let $$$S_0$$$ denote the set of elements $$$i$$$ such that $$$i$$$ has the same $$$0$$$-th bit as $$$p_n$$$, and $$$P_0$$$ denote the set of elements $$$i$$$ ($$$1\le i\le n - 1$$$) such that $$$p_i$$$ has the same $$$0$$$-th bit as $$$p_n$$$. $$$\sum_{i\in P_0} \text{bit}_1(p_i) = \left(\sum_{i\in S_0} \text{bit}_1(i)\right) - \text{bit}_1(p_n)$$$, so the $$$1$$$-st bit of $$$p_n$$$ is zero if $$$\sum_{i\in P_0} \text{bit}_1(p_i) = \sum_{i\in S_0} \text{bit}_1(i)$$$.

In general, we can let $$$S_k$$$ denote the set of elements $$$i$$$ such that $$$i$$$ has the same $$$0$$$-th, $$$1$$$-st, $$$\ldots$$$ , $$$k$$$-th bit as $$$p_n$$$, and $$$P_k$$$ denote the set of elements $$$i$$$ ($$$1\le i\le n - 1$$$) such that $$$p_i$$$ has the same $$$0$$$-th, $$$1$$$-st, $$$\ldots$$$ , $$$k$$$-th bit as $$$p_n$$$. Then, the $$$k$$$-th bit of $$$p_n$$$ is zero if $$$\sum_{i\in P_{k-1}} \text{bit}_k(p_i) = \sum_{i\in S_{k-1}} \text{bit}_k(i)$$$.

Observe that $$$|P_k| \le \left\lceil \frac{|P_{k - 1}|}{2} \right\rceil$$$ for all $$$k\ge 1$$$. Hence, the total number of queries used is

def query(index,num):
    print("?",index,num)
    return int(input())

def main():
    n = int(input())
    rest = set()
    likely = set()
    for i in range(1,n):
        rest.add(i)
    for i in range(1,n+1):
        likely.add(i)
    D = len(bin(n)[2:])
    ans = 0
    for d in range(D):
        index_0 = set()
        index_1 = set() 
        likely_0 = set()
        likely_1 = set()
        for index in rest:
            res = query(index, 1<<d)   
            if res == 0:
                index_0.add(index)
            else:
                index_1.add(index)  
        zeros = 0
        ones = 0  
        for num in likely:
            if num & (1<<d):
                ones += 1
                likely_1.add(num)
            else:
                zeros += 1
                likely_0.add(num)
        if zeros == len(index_0):
            ans += 1 << d
            rest = index_1
            likely = likely_1
        elif ones == len(index_1):
            rest = index_0
            likely = likely_0
        else:
            print("Error")
            return 
    print("!",ans)

T = int(input())
t = 1
while t <= T:
    main()
    t += 1

Great

Good

Neutral

Bad

Didn't Solve

Read the above hints before continuing.

As noted in Hint 1.2, we can binary search on the target beauty $$$g$$$.

For each index $$$1 \le i \le n$$$, recall that $$$f_g(a, i)$$$ is the number of indices $$$j\neq i$$$ satisfying $$$a_{\max(i, j)} - a_{\min(i, j)} \ge g$$$.

As mentioned in Hint 3, we only care whether $$$f_g(a, i)$$$ is $$$0$$$, $$$1$$$, $$$2$$$, or greater than $$$2$$$. We iterate through $$$i = 1, \ldots, n$$$, and maintain the three smallest previous values $$$a_j$$$ (for $$$j \lt i$$$). For each of these, we check whether the condition holds and increment both $$$f_g(a, i)$$$ and $$$f_g(a, j)$$$ if it does. This leads to an $$$\mathcal{O}(3n) = \mathcal{O}(n)$$$ computation per $$$g$$$.

We simulate each possible first move $$$p$$$ by Hao. Let array $$$b$$$ be array $$$a$$$ after removing index $$$p$$$. When Hao removes index $$$p$$$, only the $$$f_g(a, p)$$$ indices $$$q$$$ satisfying $$$|a_p - a_q| \ge g$$$ will have their $$$f_g(b, q) = f_g(a, q) - 1$$$, while all others remain unchanged.

Hao succeeds in keeping the beauty below $$$g$$$ if and only if removing index $$$p$$$ results in all $$$f_g(b, i) \le 1$$$. Equivalently, the indices $$$q$$$ paired with $$$p$$$ must include all indices that initially had $$$f_g(a, i) = 2$$$.

If no such removal $$$p$$$ works, Alex can achieve his goal of keeping the beauty at least $$$g$$$.

Checking each first move $$$p$$$ requires $$$\mathcal{O}(f_g(a, p))$$$ time, and summing up over $$$\sum_{1\le p\le n} f_g(a, p) \le 2(3n) = \mathcal{O}(n)$$$ since we only maintain at most three previous values of $$$a_j$$$ (for $$$j \lt i$$$) during the calculation of $$$f_g(a, i)$$$.

The total time complexity is $$$\mathcal{O}(n \log_2 10^9)$$$ since we perform a binary search over $$$g$$$ and compute $$$f_g(a, i)$$$ in linear time per iteration.

def main():
    n = int(input())
    arr = list(map(int,input().split()))

    # calculate the number of j for each i that satisfy arr[max(i,j)] - arr[min(i,j)] >= target
    def measurecount(arr,target):
        m = len(arr)
        count = [0]*m
        minimum = []
        for i in range(m):
            for j in range(len(minimum)):
                if minimum[j] + target <= arr[i]:
                    count[i] += 1
            minimum.append(arr[i])
            minimum.sort()
            if len(minimum) > 3:
                minimum.pop()
        maximum = []
        for i in range(m-1,-1,-1):
            for j in range(len(maximum)):
                if maximum[j] - target >= arr[i]:
                    count[i] += 1
            maximum.append(arr[i])
            maximum.sort(reverse=True)
            if len(maximum) > 3:
                maximum.pop()
        return count

    # binary search to judge if we can find such pair
    def judge(target):
        count = measurecount(arr,target)
        if max(count) <= 1:
            return False
        pick = []
        if max(count) > 2:
            for i in range(n):
                if count[i] > 2:
                    pick = [i]
                    break
        else:
            for i in range(n):
                if count[i] != 2: 
                    continue 
                for j in range(n):
                    if j==i: 
                        pick.append(j)
                    elif j < i and arr[j] + target <= arr[i]: 
                        pick.append(j)
                    elif j > i and arr[i] + target <= arr[j]:
                        pick.append(j)
                break

        for p in pick:
            count2 = measurecount(arr[:p]+arr[p+1:], target)
            if max(count2) <= 1:
                return False
        return True       

    front = -10**9 - 10
    rear = 10**9 + 10
    while front < rear:
        mid = front + (rear-front)//2
        res = judge(mid)
        if res:
            front = mid + 1
        else:
            rear = mid 
    ans = front - 1
    print(ans)
                       
T = int(input())
t = 1
while t <= T:
    main()
    t += 1
    

#include "bits/stdc++.h"
using namespace std;
 
const int MAXN = 200005;
const int INF = 1000000005;
 
inline int fdiv(int num, int denom) {
  return num / denom - ((num ^ denom) < 0 && num % denom);
}
inline int cdiv(int num, int denom) { return fdiv(num + denom - 1, denom); }
 
int t;
int n;
int a[MAXN];
 
vector<int> adj[MAXN];
void add_edge(int u, int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}
bool check(int x) {
  for (int i = 1; i <= n; i++) {
    adj[i].clear();
  }
  set<pair<int, int>> st;
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (auto [prv, prv_id] : st) {
      if (a[i] - prv >= x) {
        add_edge(prv_id, i);
      }
    }
    st.insert({a[i], i});
    if ((int) st.size() > 3) {
        st.erase(prev(st.end()));
    }
  }
 
  int bad_cnt = 0;
  for (int i = 1; i <= n; i++) {
    if ((int)adj[i].size() >= 2) {
      bad_cnt++;
    }
  }
  for (int i = 1; i <= n; i++) {
    int delta = (int)adj[i].size() >= 2;
    for (int v : adj[i]) {
      if (adj[v].size() == 2) {
        delta++;
      }
    }
    if (delta == bad_cnt) {
      return false;
    }
  }
  return true;
}
 
int main() {
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    int lo = -INF, hi = INF;
    while (lo < hi) {
      int mid = cdiv(lo + hi, 2);
      if (check(mid)) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    cout << lo << '\n';
  }
  return 0;
}

Great

Good

Neutral

Bad

Didn't Solve

Great

Good

Neutral

Bad

Didn't Solve

You should Read Editorial of F1 First

Let the initial permutation be $$$p=(p_1,p_2,\dots,p_n)$$$, and let the final array be $$$q=(q_1,q_2,\dots,q_n)$$$. Initialize $$$q_i=0$$$ for all $$$i$$$, meaning every position in the output is still undetermined. During the $$$t$$$-th iteration, find the smallest index $$$i$$$ whose value can be decreased to $$$t$$$. Repeatedly choose this $$$i$$$, locate indices $$$j,k$$$ such that $$$p_i=\max(p_j,p_k)+1$$$ and $$$p_i=\min(p_j,p_k)+2$$$, and perform the updates $$$p_i\leftarrow p_i-2$$$, $$$p_j\leftarrow p_j+1$$$, $$$p_k\leftarrow p_k+1$$$. This is equivalent to removing $$$p_i$$$ and setting $$$q_i\gets t$$$. After removing $$$p_i$$$, the remaining elements $$$p_1,\dots,p_{i-1},p_{i+1},\dots,p_n$$$ close the gap (preserving relative order), forming a permutation of length $$$n-1$$$.

This remove-and-assign simulation can be supported by a Fenwick tree or a segment tree so that each update and query runs in $$$\mathcal{O}(\log n)$$$ time; however, naively finding the correct index $$$i$$$ could still cost $$$\mathcal{O}(n)$$$ per step. Define the rank of $$$p_i$$$ as the number of alive (not yet removed) elements that are not greater than $$$p_i$$$, including $$$p_i$$$ itself.

To speed up the process, keep a pointer at the smallest alive index $$$i$$$ and check its rank. If the rank is odd, remove this element immediately. If the rank is even, move the pointer to the next smaller element to its right, that is, to the smallest $$$ j \gt i$$$ with $$$p_j \lt p_i$$$. Continue until you reach an element with odd rank.

Although a single "move to the next smaller on the right" step may look linear, the total number of such moves over the whole algorithm is at most $$$2n$$$. If an element is first visited when its rank is even, after some element to its right is removed, its rank becomes odd the next time it is visited; if an element’s rank is already odd, it is removed immediately upon visit. Therefore each index is visited at most twice.

To implement this, we maintain two data structures:

1. A Fenwick tree over values, where a $$$1$$$ at position $$$p_i$$$ indicates that the value $$$p_i$$$ is still alive (and $$$0$$$ otherwise). This lets you query the current rank of $$$p_i$$$ in $$$\mathcal{O}(\log n)$$$ time.

2. Let $$$ip$$$ denote the array that is the inverse of $$$p$$$, i.e., $$$ip_{p_i} = i$$$. Store a range-min segment tree over the array $$$ip$$$ . When the value $$$p_i$$$ is removed, set $$$ip_{p_i}=\infty$$$. If the current visited index is $$$i$$$, then a range-min query on $$$[1,p_i-1]$$$ returns the minimum position $$$j$$$ such that $$$j \gt i$$$ and $$$p_j \lt p_i$$$ (the next smaller element on the right by value). Each query and update costs $$$\mathcal{O}(\log n)$$$, and each index is examined at most twice, so the overall complexity is $$$\mathcal{O}(n\log n)$$$, which is sufficient for the F2 constraints.

inf = 10**9

class fenwick(object):
    def __init__(self, n):
        self.n = n
        self.cul = [0]*n
        self.maxd = len(bin(n))-3
    def update(self,index,diff):
        i = index
        while i<self.n:
            self.cul[i] += diff
            i += (i+1)&(-i-1)
    def getaccu(self,index):
        output = 0
        i = index
        while i>=0:
            output += self.cul[i]
            i -= (i+1)&(-i-1)
        return output

class segment_tree(object):
    def merge(self,num,accu):
        return min(accu,num)
    def __init__(self,n,initial):
        self.n = n
        self.inf = inf
        self.arr = [self.inf]*(2*n)
        for i in range(2*n-1,0,-1):
            if i>=n:  self.arr[i] = initial[i-n]
            else:     self.arr[i] = self.merge(self.arr[2*i],self.arr[2*i+1])

    def update(self,index,target):
        index += self.n
        self.arr[index] = target
        while index > 0:
            if index & 1:
                nexttarget = self.merge( self.arr[index], self.arr[index-1])
            else:
                nexttarget = self.merge( self.arr[index], self.arr[index+1])
            self.arr[index>>1] = nexttarget
            index = index >> 1

    def addnum(self,index,diff):
        self.update(index, self.arr[index+self.n] + diff)

    def query(self,left,right):
        i,j = self.n+left,  self.n+right+1
        output = self.inf  # initial output should be changed if you want to change the merge function
        while i<j:
            if i&1:
                output = self.merge(self.arr[i],output)
                i += 1
            if j&1:
                j -= 1
                output = self.merge(self.arr[j],output)
            i = i >> 1
            j = j >> 1
        return output

def main(t):
    n = int(input())
    p = list(map(int,input().split()))
    location = [0]*n
    for i in range(n):
        p[i] -= 1
        location[p[i]] = i 
    seg = segment_tree(n, location)
    fen = fenwick(n)
    for i in range(n):
        fen.update(i,1)
    ans = [-1]*n
    curr = 1
    for i in range(n):
        if ans[i] >= 0:  
            continue 
        index = fen.getaccu(p[i]) - 1
        if index % 2 == 0:
            fen.update(p[i],-1)
            seg.update(p[i],inf)
            ans[i] = curr 
            curr += 1
            continue
        j = i 
        while True:
            j = seg.query(0,p[j]-1) 
            nextindex = fen.getaccu(p[j]) - 1
            if nextindex % 2 > 0:
                continue 
            break
        ans[j] = curr 
        ans[i] = curr + 1
        curr += 2
        seg.update(p[i],inf)
        seg.update(p[j],inf)
        fen.update(p[i],-1)
        fen.update(p[j],-1)
    print(*ans)

T = int(input())
for t in range(T):
    main(t)

Great

Good

Neutral

Bad

Didn't Solve

We can obtain $$$n$$$ from the binary representation as following

We know that the fact

Let’s consider the last active bit i.e. $$$\mathtt{1}$$$ is $$$i$$$ then $$$n$$$ as integer is

thus the answer is the index of last occurrence of $$$\mathtt{1}$$$ , Complexity $$$O(n)$$$.

for _ in range(int(input())):
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        if(s[i]=='1'):
            ans=n-i-1
            break
    print(ans)

Maintain two arrays $$$b$$$ and $$$c$$$ such that

Now , maintain a function $$$f$$$ that process the maximum subarray sum in $$$O(n)$$$ for both of arrays $$$b$$$ and $$$c$$$ (Kadane's Algorithm for example), be careful of initialization that it’s non-empty , and the answer is $$$\max(f(b),f(c))$$$ , Complexity $$$O(n)$$$.

def f(a):
    best = a[0]  
    sum = a[0]   
    for i in range(1, len(a)): 
        sum = max(a[i], sum + a[i])
        best = max(best, sum)
    return best

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = a.copy()
    c = a.copy()
    for i in range(n):
        b[i] //= k
        c[i] *= k
    print(max(f(b), f(c)))

One way to solve the problem is to make a fixed-size sub-array and iterate through the array and test all the subarrays with length $$$k$$$ i.e Sliding window of length $$$k$$$ , so we can make a sliding window with length $$$k$$$ and iterate the array which yields $$$n- k + 1$$$ and you delete $$$k − 1$$$ elements in total then the total complexity for each case can reach $$$O(n^2)$$$ ,Unfortunately it’s not efficient enough so we should optimize!. We can optimize the solution by making a frequency map ; we use a greedy approach by removing the first $$$k$$$ elements from Map (dict) structure , and then doing a sliding window minimum and finally obtain the minimum final number of distinct numbers , total complexity is $$$O(n \log n)$$$ due to using maps.

def solve():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a = [str(arr[i]) for i in range(n)]
    dic = {}
    for num in a:
        if num not in dic:   dic[num] = 0
        dic[num] += 1
    for i in range(k):
        dic[a[i]] -= 1
        if dic[a[i]]==0:  del dic[a[i]]
    ans = len(dic)
    for i in range(k,n):
        if a[i-k] not in dic:  dic[a[i-k]] = 0
        dic[a[i-k]] += 1
        dic[a[i]] -= 1
        if dic[a[i]]==0:  del dic[a[i]]
        ans = min(ans, len(dic))
    print(ans)

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

Let's see for each index $$$i$$$ among the permutation $$$p_n$$$ , what's the count of possible cases for it , we can use $$$(n-i)$$$ integers , thus for each index $$$i$$$ the count is $$$2^{n-i}$$$ , thus the answer will be the sum of count overall indices

due to exclusion of last index , complexity is $$$O(\log n)$$$ (Binary Exponentiation).

m=10**9+7
def p(a,b,m):
    a%=m
    r=1
    while(b>0):
        if(b&1):
            r=r*a%m
        a=a*a%m
        b>>=1
    return r
def ff(n):
    return (p(2,n,m)-n-1)%m
for _ in range(int(input())):
  n=int(input())
  print(ff(n))

the given condition is $$$x \le i \le j \le y$$$, which implies $$$i \le j$$$, meaning we don't have to consider elements with $$$i \gt j$$$, and can set to $$$0$$$. Now, what if we find sum of $$$g[i][j]$$$, such that $$$x \le i, j \le y$$$ , The indices which do not satisfy $$$i \le j$$$ are set to $$$0$$$, meaning that it doesn't affect the answer. Thus, it's enough to output the sum of integers of the new grid's sub-grid $$$(x, x)$$$ to $$$(y, y)$$$ per query, which can be done using 2d prefix sum.

#include<bits/stdc++.h>

using namespace std;

long long cbz(int fx,int fy,int tx,int ty,vector<vector<long long>> &bsum){
    if(fx>tx || fy>ty){return 0;}
    if(fx==0 && fy == 0){return bsum[tx][ty];}
    else if(fx==0){
        return bsum[tx][ty]-bsum[tx][fy-1];
    }
    else if(fy==0){
        return bsum[tx][ty]-bsum[fx-1][ty];
    }
    else{
        return bsum[tx][ty]-bsum[tx][fy-1]-bsum[fx-1][ty]+bsum[fx-1][fy-1];
    }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,q;
  cin >> n >> q;
  vector<vector<long long>> a(n,vector<long long>(n,0));
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin >> a[i][j];
    }
  }
  auto rs=a;
  for(int i=0;i<n;i++){
    for(int j=1;j<n;j++){rs[i][j]+=rs[i][j-1];}
  }
  for(int i=1;i<n;i++){
    for(int j=0;j<n;j++){rs[i][j]+=rs[i-1][j];}
  }
  auto ts=a;
  for(int i=1;i<n;i++){
    for(int j=0;j<n;j++){ts[i][j]+=ts[i-1][j];}
  }
  for(int j=1;j<n;j++){
    for(int i=1;i<n;i++){
      ts[i][j]+=ts[i-1][j-1];
    }
  }
  // for(auto &nx : ts){
  //   for(auto &ny : nx){
  //     cout << ny << " ";
  //   }cout << "\n";
  // }
  while(q>0){
    q--;
    int l,r;
    cin >> l >> r;
    l--; r--;
    long long res=ts[r][r];
    // cout << res << "\n";
    if(l>0){
      res-=cbz(0,l,l-1,r,rs);
      res-=ts[l-1][l-1];
    }
    cout << res << "\n";
  }
  return 0;
}

Let's say $$$x=0$$$ for all the queries. Then, we can sort all the queries by $$$y$$$, and setup a segment tree(XOR). From the smallest $$$y$$$, we check all integers in the array which are $$$\le y$$$, and update them in segment tree. Now, for each query it's simple range XOR query on segtree.

What if that's not the case, and $$$x \gt 0$$$ ? Then the answer for query l r x y is (l r 0 x-1) ^ (l r 0 y), both of which can be processed using the method above. At most, he have to process $$$2q$$$ queries of type l r 0 y

#include<bits/stdc++.h>

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>


#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

using namespace std;
using namespace atcoder;

long long op(long long x,long long y){
  return (x^y);
}
long long e(){
  return 0;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n,q;
    cin >> n >> q;
    vector<array<long long,3>> ev;
    for(long long i=0;i<n;i++){
      long long a;
      cin >> a;
      ev.push_back({a,0,i});
    }
    vector<int> l(q),r(q);
    vector<long long> res(q);
    for(int i=0;i<q;i++){
      cin >> l[i] >> r[i];
      l[i]--;
      long long x,y;
      cin >> x >> y;
      ev.push_back({x-1,1,i});
      ev.push_back({y,1,i});
    }
    sort(ev.begin(),ev.end());
    segtree<long long,op,e> seg(n);
    for(auto &nx : ev){
      // cerr << nx[0] << " " << nx[1] << " " << nx[2] << "\n";
      if(nx[1]==0){
        seg.set(nx[2],nx[0]);
      }
      else{
        res[nx[2]]^=seg.prod(l[nx[2]],r[nx[2]]);
      }
    }
    for(auto &nx : res){cout << nx << "\n";}
  }
  return 0;
}

notice that the set of prime factors common between numerator and denumerator are the same and in the numerator for each power of common it’s at least has the same power as den and We’re aiming to minimize the product thus we need to make a divisible by b (for each prime separately) so whenever we had an even power for some prime the best thing is split it into equal parts.

Calculate sieve for all numbers upto $$$2 \cdot 10^5$$$ this can be achieved in $$$O(n \log(\log(n)))$$$ which is fast , Find the prime factorization of $$$n!$$$ this can be found with the prime factorization form of $$$n!$$$

For each prime factor $$$p_i$$$ the power $$$\alpha_i$$$ can be calculated with the following formula

it can be show that this sum converges in $$$a$$$ , $$$O(\log(n))$$$ it’ll take no more than $$$20$$$ runs , thus the final prime factorization will take $$$O(20p)$$$.

Now we want to have $$$a \bmod b = 0$$$ (assuming fraction $$$\frac{a}{b}$$$) , so a productive greedy is to have for each $$$p_i$$$ with power $$$\alpha_i$$$ the following : for $$$a$$$ the power is $$$\displaystyle \left \lceil \frac{\alpha_i}{2} \right \rceil$$$ and for $$$b$$$ the power is $$$\displaystyle \left \lfloor \frac{\alpha_i}{2} \right \rfloor$$$.

Therefore we only need to look at $$$\alpha_i \bmod 2 = 1$$$ i.e. odd powers , and calculate The following

For each test case , we calculate for each prime upto $$$n$$$ it’s power , the count of prime upto $$$n$$$ are approximately $$$O \left ( \frac{n}{\log(n)} \right )$$$ and we check the power in $$$O(\log(n))$$$ and even better in practice , this yields prime factorization of $$$n!$$$ takes at most $$$O(n)$$$ time , we can with each prime factorized if the final power is odd then multiply it by the answer and take the modulus by $$$10^9 + 7$$$ , thus the total complexity for multiple test cases is $$$O(8 \cdot 10^5)$$$ for precalculation of sieve (primes) , and $$$O(\sum n)$$$ for answering test cases.

def solve():
    x = int(input())
    ip= [1] * (x + 1)
    ip[0] = ip[1] = 0
    for i in range(2, int(x**0.5) + 1):
        if ip[i]:
            for j in range(i * i, x + 1, i):
                ip[j] = 0
    p = [0] * (x + 1)
    for i in range(2, x + 1):
        if ip[i]:
            cnt = 0
            j = i
            while j <= x:
                cnt += x // j
                if j > x // i: break
                j *= i
            p[i] = cnt
    ans = 1
    MOD = 10**9 + 7
    for i in range(2, x + 1):
        if p[i] % 2:
            ans = (ans * i) % MOD
    print(ans)

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

can be done with simple Treap, or using offline queries and an ordered set / segtree and array recovery with answering/handling queries in reverse, or sqrt decomposition.

#include<bits/stdc++.h>

using namespace std;

#define SZ 250

vector<vector<long long>> dat={{}};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int q;
  cin >> q;
  while(q>0){
    q--;
    int typ;
    cin >> typ;
    if(typ==1){
      long long i,x;
      cin >> i >> x;
      bool rb=false;
      for(auto &nx : dat){
        if(i<=nx.size()){
          nx.insert(nx.begin()+i,x);
          if(nx.size()>2*SZ){rb=true;}
          break;
        }
        i-=nx.size();
      }
      if(rb){
        // rebuild
        vector<long long> v;
        for(auto &nx : dat){
          for(auto &ny : nx){v.push_back(ny);}
          nx.clear();
        }
        dat.clear();
        int vl=v.size();
        dat.resize((vl/SZ)+1);
        for(int i=0;i<vl;i++){
          dat[i/SZ].push_back(v[i]);
        }
      }
    }
    else{
      int i;
      cin >> i;
      i--;
      for(auto &nx : dat){
        if(i<nx.size()){
          cout << nx[i] << "\n";
          break;
        }
        i-=nx.size();
      }
    }
  }
  return 0;
}

simple centroid decomposition problem, precomputing the answers for each centroid using prefix sums and answering the queries in $$$O(\log n)$$$ or $$$O(\log^2 n)$$$ depending on the implementation, and using the fact that $$$q(l, r) = q(1, r) - q(1, l-1)$$$.

// https://judge.yosupo.jp/submission/102080

#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_range_contour_sum_on_tree"

#include <iostream>

#include <algorithm>
#include <array>
#include <cassert>
#include <deque>
#include <iostream>
#include <queue>
#include <random>
#include <utility>
#include <vector>

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct PointAddRangeContourSumOnTree {
        using value_type = T;
    private:
        struct InternalSegmentTree {
            InternalSegmentTree(int n = 0) : _n(n), _dat(n + 1, e()) {}
            template <typename InputIterator>
            InternalSegmentTree(InputIterator first, InputIterator last) : _n(last - first), _dat(2 * _n, e()) {
                for (int i = 0; i < _n; ++i) _dat[_n + i] = *first++;
                for (int i = _n - 1; i > 0; --i) _dat[i] = op(_dat[2 * i], _dat[2 * i + 1]);
            }
            void add(int i, const value_type& val) {
                for (i += _n; i; i >>= 1) _dat[i] = op(_dat[i], val);
            }
            value_type sum(int l, int r) const {
                l = std::max(0, l), r = std::min(r, _n);
                value_type res = e();
                for (l += _n, r += _n; l < r; l >>= 1, r >>= 1) {
                    if (l & 1) res = op(res, _dat[l++]);
                    if (r & 1) res = op(res, _dat[--r]);
                }
                return res;
            }
        private:
            int _n;
            std::vector<value_type> _dat;
        };
        using sequence_type = InternalSegmentTree;

        struct AuxInfo {
            int8_t child_index;
            int dep;
        };

        struct TreeNode {
            std::vector<int> adj;
            typename std::array<AuxInfo, 30>::iterator info_it;
            value_type dat;
        };
    public:
        PointAddRangeContourSumOnTree(int n = 0, const value_type& fill_value = e()) : PointAddRangeContourSumOnTree(std::vector<value_type>(n, fill_value)) {}
        PointAddRangeContourSumOnTree(const std::vector<value_type>& a) : _n(a.size()), _nodes(_n), _par(2 * _n, -1), _info(_n), _subtrees(2 * _n), _ord(_n) {
            for (int i = 0; i < _n; ++i) _nodes[i].dat = a[i];
        }

        void add_edge(int u, int v) {
            _nodes[u].adj.push_back(v);
            _nodes[v].adj.push_back(u);
        }

        // O(NlogN)
        void build() {
            std::mt19937 rng{ std::random_device{}() };
            reorder(std::uniform_int_distribution<int>{ 0, _n - 1 }(rng));

            int new_node = _n;
            std::vector<int> sub_size(2 * _n, 0);
            std::vector<int> ctr(2 * _n, -1);

            std::vector<int> head(2 * _n), tail(2 * _n), link(2 * _n);
            for (int i = 0; i < _n; ++i) head[i] = tail[i] = i;

            std::vector<value_type> dat(_n);

            auto rec = [&](auto rec, int r, int siz) -> int {
                int c = -1;
                auto get_centroid = [&](auto get_centroid, int u, int p) -> void {
                    sub_size[u] = 1;
                    for (int v : _nodes[u].adj) if (v != p) {
                        get_centroid(get_centroid, v, u);
                        if (v == c) {
                            sub_size[u] = siz - sub_size[c];
                            break;
                        }
                        sub_size[u] += sub_size[v];
                    }
                    if (c < 0 and sub_size[u] * 2 > siz) c = u;
                };
                get_centroid(get_centroid, r, -1);

                for (int v : _nodes[c].adj) {
                    const int comp_size = sub_size[v];
                    _nodes[v].adj.erase(std::find(_nodes[v].adj.begin(), _nodes[v].adj.end(), c));
                    ctr[v] = rec(rec, v, comp_size);
                    sub_size[v] = comp_size;
                }

                auto comp = [&](int i, int j) { return sub_size[i] > sub_size[j]; };
                std::priority_queue<int, std::vector<int>, decltype(comp)> pq{ comp };

                for (int v : _nodes[c].adj) {
                    link[v] = -1;
                    pq.push(v);
                }

                auto build_sequence = [&, this](const int root_head, const bool child_index) {
                    std::deque<std::pair<int, int>> dq;
                    for (int root = root_head; root >= 0; root = link[root]) dq.emplace_back(root, -1);
                    value_type sum = e();
                    auto dat_it = dat.begin();
                    int nxt = -1;
                    while (dq.size()) {
                        const auto [u, pu] = dq.front();
                        dq.pop_front();
                        if (u == nxt) *dat_it++ = std::exchange(sum, e()), nxt = -1;
                        auto& node = _nodes[u];
                        *node.info_it++ = { child_index, int(dat_it - dat.begin()) };
                        sum = op(sum, node.dat);
                        for (int v : node.adj) if (v != pu) {
                            dq.emplace_back(v, u);
                            if (nxt < 0) nxt = v;
                        }
                    }
                    *dat_it++ = sum;
                    return sequence_type(dat.begin(), dat_it);
                };

                while (pq.size() >= 2) {
                    const int u = pq.top(); pq.pop();
                    const int v = pq.top(); pq.pop();
                    if (pq.empty()) {
                        _par[ctr[u]] = _par[ctr[v]] = c;
                        _subtrees[c][0] = build_sequence(head[u], 0);
                        _subtrees[c][1] = build_sequence(head[v], 1);
                        break;
                    }
                    sub_size[new_node] = sub_size[u] + sub_size[v];
                    ctr[new_node] = new_node;
                    _par[ctr[u]] = _par[ctr[v]] = new_node;
                    _subtrees[new_node][0] = build_sequence(head[u], 0);
                    _subtrees[new_node][1] = build_sequence(head[v], 1);
                    head[new_node] = head[u], tail[new_node] = tail[v], link[tail[u]] = head[v];
                    pq.push(new_node);
                    ++new_node;
                }
                if (pq.size()) {
                    int u = pq.top(); pq.pop();
                    _par[ctr[u]] = c;
                    _subtrees[c][0] = build_sequence(head[u], 0);
                }
                for (int v : _nodes[c].adj) _nodes[v].adj.push_back(c);
                return c;
            };
            rec(rec, 0, _n);
            _par.resize(new_node), _par.shrink_to_fit();
            _subtrees.resize(new_node), _subtrees.shrink_to_fit();
        }

        // O(1)
        value_type get(int u) const {
            u = _ord[u];
            return _nodes[u].dat;
        }
        // O((logN)^2)
        void add(int u, const value_type& val) {
            u = _ord[u];
            _nodes[u].dat = op(_nodes[u].dat, val);
            int v = _par[u];
            const auto it_end = _nodes[u].info_it;
            for (auto it = _info[u].begin(); it != it_end; ++it) _subtrees[std::exchange(v, _par[v])][it->child_index].add(it->dep, val);
        }
        // O((logN)^2)
        value_type sum(int u, int dl, int dr) const {
            u = _ord[u];
            value_type res = dl <= 0 and 0 < dr ? _nodes[u].dat : e();
            res = op(res, _subtrees[u][0].sum(dl - 1, dr - 1));
            res = op(res, _subtrees[u][1].sum(dl - 1, dr - 1));
            int v = _par[u];
            const auto it_end = _nodes[u].info_it;
            for (auto it = _info[u].begin(); it != it_end; ++it) {
                const int ql = dl - it->dep - 1, qr = dr - it->dep - 1;
                if (v < _n and ql <= 0 and 0 < qr) res = op(res, _nodes[v].dat);
                res = op(res, _subtrees[std::exchange(v, _par[v])][it->child_index ^ 1].sum(ql - 1, qr - 1));
            }
            return res;
        }

    private:
        int _n;
        std::vector<TreeNode> _nodes;
        std::vector<int> _par;
        std::vector<std::array<AuxInfo, 30>> _info;
        std::vector<std::array<sequence_type, 2>> _subtrees;

        std::vector<int> _ord;

        void reorder(int s) {
            _ord.assign(_n, -1);
            int t = 0;
            std::deque<int> dq{ s };
            while (dq.size()) {
                int u = dq.front(); dq.pop_front();
                _ord[u] = t++;
                for (int v : _nodes[u].adj) if (_ord[v] < 0) dq.push_back(v);
            }
            assert(t == _n);
            std::vector<TreeNode> tmp(_n);
            for (int i = 0; i < _n; ++i) {
                for (int& elm : _nodes[i].adj) elm = _ord[elm];
                _nodes[i].info_it = _info[_ord[i]].begin();
                tmp[_ord[i]] = std::move(_nodes[i]);
            }
            _nodes.swap(tmp);
        }
    };
} // namespace suisen

long long op(long long x, long long y) {
    return x + y;
}
long long e() {
    return 0;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    std::vector<long long> a(n);
    for (auto &e : a) std::cin >> e;

    suisen::PointAddRangeContourSumOnTree<long long, op, e> g(a);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        u--; v--;
        g.add_edge(u, v);
    }
    g.build();

    while (q --> 0) {
        // int query_type;
        // std::cin >> query_type;
        // if (query_type == 0) {
        //     int p, x;
        //     std::cin >> p >> x;
        //     g.add(p, x);
        // } else {
            int p, l, r;
            std::cin >> p >> l >> r;
            p--;
            r++;
            std::cout << g.sum(p, l, r) << '\n';
        // }
    }

    return 0;
}