You just need to count number of zeroes and number of ones and compare them . Time Complexity is $$$O(n)$$$

/*
Author : ayuxh
*/
#include <bits/stdc++.h> 
using namespace std;
#define INF (int)2e9
#define INFL (long long)2e18
#define int long long
const int mod = (int)1e9+7;
 
void Solve(){
    int n,inp;
    cin>>n;
    int cntz=0;
    for(int i=0;i<n;i++){
        cin>>inp;
        if(inp==0) cntz++;
    }
    int cnto=n-cntz;
    if(cntz==cnto)    cout<<"TIE\n";
    else if(cntz>cnto)    cout<<"ALICE\n";
    else    cout<<"BOB\n";
}
 
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    for (int i = 1; i <= t; i++)
    {
        Solve();
    }
    return 0;
}

You can precompute all the primes less than equal to $$$10^5$$$ and for $$$10^5$$$ the ans is $$$100003$$$ .

Store it in an array and then you can answer each query by using lower_bound for binary search or search linearly .

You can also use "sieve of eratosthenes" for faster precomputation .

Time Complexity for precomputation is $$$O(n\sqrt{n})$$$ and for each query $$$log n$$$ .

/*
Author : ayuxh
*/
#include <bits/stdc++.h>
using namespace std;
#define INF (int)2e9
#define INFL (long long)2e18
#define int long long
const int mod = (int)1e9+7;
 
vector<int> primes; 
bool isPrime(int num){
    if(num==1)  return false;
    for(int i=2;i*i<=num;i++){
        if(num%i==0)    return false;
    }
    return true;
}
void Solve(){
    int n;
    cin>>n;
    int pos=lower_bound(primes.begin(),primes.end(),n)-primes.begin();
    cout<<primes[pos]<<"\n";
}
 
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    //precomputing
    int N=100005;
    for(int n=1;n<=N;n++){
        if(isPrime(n))  primes.push_back(n);
    }

    for (int i = 1; i <= t; i++)
    {
        Solve();
    }
    return 0;
}

Note : $$$a | b >= max(a, b)$$$ where $$$|$$$ is bitwise or , thus if we choose more elements our value will increase or remain same ,thus we can choose maximum number of elements we can , since more number of elements never decreases the bitwise or value .

Notice if the length of given array is even then we can choose the entire array . Else we need to skip choosing one element .

Thus for each index we can find the bitwise or of the remaining elements if current index is skipped . This can be done easily by precomputing the prefix or and suffix or for the array .

At each index $$$i$$$ the or of remaining elements is or of prefix upto $$$i-1$$$ and suffix from $$$i+1$$$ .

Thus we can find the maximum value iterating over all $$$i$$$.

Time Complexity for precomputation is $$$O(n)$$$ and for finding the ans is $$$O(n)$$$ .

/*
Author : ayuxh
*/
#include <bits/stdc++.h>
using namespace std;
#define INF (int)2e9
#define INFL (long long)2e18
#define int long long
const int mod = (int)1e9+7;

void Solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> pref(n),suff(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int val=0;
    for(int i=0;i<n;i++){
        val|=a[i];
        pref[i]=val;
    }
    val=0;
    for(int i=n-1;i>=0;i--){
        val|=a[i];
        suff[i]=val;
    }
    if(n%2==0){
        cout<<pref[n-1]<<"\n";
        return;
    }

    int ans=0;
    for(int i=0;i<n;i++){
        int curAns=0;
        if(i-1>=0)  curAns|=pref[i-1];
        if(i+1<n)   curAns|=suff[i+1];
        ans=max(ans,curAns);
    }

    cout<<ans<<"\n";
}
 
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    for (int i = 1; i <= t; i++)
    {
        Solve();
    }
    return 0;
}

Let us calculate and store in an array the score of Mahi for all value of $$$x$$$ for $$$(0\leq x \leq n)$$$ where $$$x$$$ is number of presentations before Mahi without considering Chiku. We also calculate this array for Chiku without considering Mahi for all value of $$$x$$$ for $$$(0\leq x \leq n)$$$ .

First we will assign position to Mahi keeping the order of other $$$n$$$ presentations same . So there are $$$n+1$$$ positions for Mahi . Now there are two cases for a each number of students $$$x$$$ before Mahi :
1. Chiku is before Mahi .
2. Chiku is after Mahi .

For Case 1:
Score for Mahi increases by one if $$$A>B$$$ or decreases by one if $$$A<B$$$ . For case 1 we iterate overall $$$y$$$ $$$(0\leq y \leq x)$$$ where y is number of presentations before Chiku and find number of times when score of Mahi is greater than score of Chiku .

For Case 2:
Score for Chiku increases by one if $$$A<B$$$ or decreases by one if $$$A>B$$$ . For case 2 we iterate overall $$$y$$$ $$$(x\leq y \leq n)$$$ where y is number of presentations before Chiku and find number of times when score of Mahi is greater than score of Chiku .

The ans is sum of counts overall positions of Mahi .

Time Complexity is $$$O(n^2)$$$

/*
Author : ayuxh
*/
#include <bits/stdc++.h> 
using namespace std;
#define INF (int)2e9
#define INFL (long long)2e18
#define int long long
const int mod = (int)1e9+7;
 
void Solve(){
    int n,a,b;
    cin>>n>>a>>b;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<int> av(n+1,0),bv(n+1,0);
    int marks=0;
    for(int i=1;i<=n;i++){
        if(v[i-1]>a)  marks--;
        else if(v[i-1]<a)   marks++;
        av[i]=marks;
    }
    marks=0;
    
    for(int i=1;i<=n;i++){
        if(v[i-1]>b)  marks--;
        else  if(v[i-1]<b)  marks++;
        bv[i]=marks;
    }
    int cnt=0;
    //First assigning position to Mahi
    for(int i=0;i<=n;i++){
        //When Chicku is before Mahi
        for(int j=0;j<=i;j++){
            int scA=av[i];
            int scB=bv[j];
            if(b>a) scA--;
            if(a>b) scA++;
            if(scA>scB) cnt++;
        }
        //When Chicku is after Mahi
        for(int j=i;j<=n;j++){
            int scA=av[i];
            int scB=bv[j];
            if(b>a) scB++;
            if(a>b) scB--;
            if(scA>scB) cnt++;
        }
    }
    cout<<cnt<<"\n";
}
 
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    for (int i = 1; i <= t; i++)
    {
        Solve();
    }
    return 0;
}

Let us make some observations in above approach for D which optimizes the solution .

1. Since we are comparing the scores of Mahi and Chiku , increasing score of Mahi is same as decreasing score of Chiku . So for both Case 1 and Case 2 if $$$A>B$$$ then increase score of Mahi by 1 else if $$$A<B$$$ then decrease score of Mahi by 1.

2. For all $$$x$$$ $$$(0\leq x \leq n)$$$ where $$$x$$$ is number of presentations before Mahi without considering Chiku :

— Case 1 We basically count number of times score of Mahi is greater than score of Chiku overall $$$y$$$ $$$(0\leq y \leq x)$$$ .

— Case 2 We basically count number of times score of Mahi is greater than score of Chiku overall $$$y$$$ $$$(x\leq y \leq n)$$$ .

— Here $$$y$$$ is number of presentations before Chiku without considering Mahi .

— Thus we can merge these cases and our problem is count number of times score of Mahi is greater than score of Chiku overall $$$y$$$ $$$(0\leq y \leq n)$$$ and since $$$y=x$$$ is in both of the cases it needs to be consider for one more time .

We store scores of Chiku for all $$$y$$$ in an array and sort it since it is same for all $$$x$$$.

We observe that score of Mahi can vary from $$$-n$$$ to $$$n$$$ , thus we can precalculate for each score of Mahi number of times score of Chiku is less than current score of Mahi in a single loop .

The count when score of Mahi is $$$i$$$ is simply the count when score of Mahi is $$$i-1 +$$$ number of times score of Chiku is $$$i-1$$$ .

Now for each $$$x$$$ we update the score of Mahi by comparing $$$A$$$ and $$$B$$$ .

Sum of these values for each $$$x$$$ is our final ans .

Time Complexity is $$$O(n)$$$

/*
Author : ayuxh
*/
#include <bits/stdc++.h> 
using namespace std;
#define INF (int)2e9
#define INFL (long long)2e18
#define int long long
const int mod = (int)1e9+7;
 
void Solve(){
    int n;
    cin>>n;
    int a,b;
    cin>>a>>b;
    vector<int> v(n);
    for(int i=0;i<n;i++)    cin>>v[i];
    vector<int> av(n+1,0),bv(n+1,0);
    int marks=0;
    for(int i=1;i<=n;i++){
        if(v[i-1]>a)  marks--;
        else if(v[i-1]<a)   marks++;
        av[i]=marks;
    }
    marks=0;
    vector<int> vv={0};
    for(int i=1;i<=n;i++){
        if(v[i-1]>b)  marks--;
        else  if(v[i-1]<b)  marks++;
        bv[i]=marks;
        vv.push_back(bv[i]);
    }
    sort(vv.begin(),vv.end());
    int cnt=0;
    vector<int> count(2*n+1,0);
    for(int i=-n;i<=n;i++){
        while(cnt<(n+1) && vv[cnt]==i-1)    cnt++;
        count[i+n]=cnt;
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        if(a>b) av[i]++;
        else if(a<b)    av[i]--;
        ans+=count[av[i]+n];
        if(av[i]>bv[i]) ans++;
    }
    cout<<ans<<"\n";
}
 
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    for (int i = 1; i <= t; i++)
    {
        Solve();
    }
    return 0;
}

We notice that :

Number of nodes $$$i$$$ for which $$$a[i] \leq k \leq b[i]$$$ $$$=$$$ Number of nodes $$$i$$$ for which $$$a[i] \leq k$$$ $$$-$$$ Number of nodes $$$i$$$ for which $$$b[i] \lt k$$$ .

To simplify subtree queries, we flatten the tree using an Euler Tour. We maintain two arrays, $$$a tour$$$ and $$$b tour$$$.

We initialize a variable $$$t = 1$$$ and perform dfs from root , when we visit a node $$$i$$$ we store its $$$a[i]$$$ value in an array $$$a tour$$$ at position $$$t$$$ and $$$b[i]$$$ in another array $$$b tour$$$ at position $$$t$$$ , then we store this position $$$t$$$ at $$$tin[i]$$$ and increase $$$t$$$ by $$$1$$$ , while exiting this node we store $$$t$$$ at $$$tout[i]$$$.
The subtree of node $$$i$$$ in these arrays is represented by indices from $$$tin[i]$$$ to $$$tout[i]-1$$$ .

Now the problem has reduced to :

For a given node $$$x$$$ find number of elements in $$$a tour$$$ that are $$$\leq k$$$ from $$$tin[x]$$$ to $$$tout[x]-1$$$ and find number of elements in $$$b tour$$$ that are $$$\leq k-1$$$ from $$$tin[x]$$$ to $$$tout[x]-1$$$ .

Now to solve this problem we use a segment tree where each node representing a segment stores a sorted vector of all the elements in its segment.

To build this segment tree for $$$[l,r]$$$ we need to merge the sorted vectors of its left and right part .

Then to find number of elements $$$\leq$$$ to a number $$$p$$$ in a segment $$$[l,r]$$$ for the vectors of all the segments between $$$[l,r]$$$ we use binary search on each vector to find number of elements $$$\leq p$$$ in each of these vectors .

Number of segments between $$$[l,r]$$$ can be atmost $$$log$$$ $$$n$$$ and for each binary search we perform $$$log$$$ $$$n$$$ operations thus for querying the answer time complexity is $$$O(log^2$$$ $$$n)$$$ per query .


To perform update operation we update all the vectors of the segments that contains that node .

To update a vector with increase operation , we find the value's last occurence in the sorted vector using upper_bound and then increase it by 1 .

For decrease operation we find its first occurence using lower_bound and decrease it by 1 .

Time complexity for update query is $$$O(log^2$$$ $$$n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
struct Seg
{ 
    int n,sz=1;
    vector<vector<int>> v;
    vector<int> comb(vector<int> l,vector<int> r)
    {   
        int i1=0,i2=0;
        int s1=l.size(),s2=r.size();
        vector<int> res(s1+s2);
        for(int i=0; i<s1+s2; i++)
        {
            if(i1==s1||(i2<s2&&l[i1]>r[i2]))
                res[i]=r[i2],i2++;
            else  
                res[i]=l[i1],i1++;
        }
        return res;
    }
    void build(int s,vector<int> a) 
    {
        n=s;
        while(sz<n)
            sz*=2;
        v.resize(2*sz);
        for(int i=0; i<n; i++)
            v[i+sz].push_back(a[i]);
        for(int i=sz-1; i>0; i--)
            v[i]=comb(v[2*i],v[2*i+1]);  
    }
    int find(int i,int a)
    {
        int j=upper_bound(v[i].begin(),v[i].end(),a)-v[i].begin();
        return j;
    }
    int get(int l,int r,int k)    
    {
        int res=0;
        for(l+=sz,r+=sz; l<r; l>>=1,r>>=1)  
        {
            if(l&1)
                res+=find(l,k),l++;
            if(r&1)
                --r,res+=find(r,k);
        }
        return res;
    }  
    void set(int i,int a)
    {
        i+=sz;
        int k=v[i][0];
        v[i][0]+=a;
        while(i>1)
        {
            i>>=1;
            if(a>0)
            {
                int x=upper_bound(v[i].begin(),v[i].end(),k)-v[i].begin()-1;
                v[i][x]++;
            }
            else  
            {
                int x=lower_bound(v[i].begin(),v[i].end(),k)-v[i].begin();
                v[i][x]--;
            }
        }
    }  
};
 
void Solve()
{
    int n;
    cin>>n;
    vector<int> a(n),b(n);
    for(int i=0; i<n; i++)
        cin>>a[i];
    for(int i=0; i<n; i++)
        cin>>b[i];
    vector<vector<int>> g(n);
    for(int i=1; i<n; i++)
    {
        int u,v;
        cin>>u>>v;
        u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> tin(n),tout(n);
    vector<int> a_tour(n),b_tour(n);
    int t=0;
    auto dfs=[&](auto self,int c,int p)->void 
    {
        a_tour[t]=a[c];
        b_tour[t]=b[c];
        tin[c]=t++;
        for(auto x:g[c])
            if(x!=p)
            {
                self(self,x,c);
            }
        tout[c]=t;
    };
    dfs(dfs,0,-1);
    Seg aa,bb;
    aa.build(n,a_tour);
    bb.build(n,b_tour);
    int q;
    cin>>q;
    while(q--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            char c;
            int i,k;
            cin>>i>>c>>k;
            i=tin[i-1];
            if(c=='a')
                aa.set(i,k);
            else  
                bb.set(i,k);
        }
        else  
        {
            int i,k;
            cin>>i>>k;
            i--;
            cout<<aa.get(tin[i],tout[i],k)-bb.get(tin[i],tout[i],k-1)<<'\n';
        }
    }
}
int main()                                                           
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    while (t--) 
        Solve();
    return 0;
}

Lets try to calculate maximum value of sum of elements that can be made 0 using given operations.

Then our answer will be $$$(total sum - maximum value)$$$.

Note that we are considering 1 based indexing of array a here.

Make a prefix sum array p of array a. Let $$$sum(l,r)$$$ denote the sum of elements of array a from $$$l$$$ to $$$r$$$. Therefore $$$sum(l,r)$$$$$$=$$$$$$p[r]$$$$$$-$$$$$$p[l-1]$$$.

Make a $$$dp$$$ array of length $$$n+1$$$ where $$$dp[i]$$$ will store the value of maximum sum of elements that can be made equal to $$$zero$$$ if last operation was applied at $$$i$$$ $$$th$$$ position. Set $$$dp[0]$$$ $$$=$$$ $$$0$$$.

Note that when last operation is applied to $$$i$$$ the subarray of length at most $$$k$$$ starting from $$$i$$$ becomes $$$0$$$ .

Let $$$l$$$ denote the maximum value of any index $$$j$$$ such that $$$j\leq i$$$ and $$$s[j]=1$$$, if no such $$$j$$$ exist set $$$l = -1$$$.

Since we apply operation on $$$i$$$ we cannot apply operation on any $$$j$$$ such that $$$l \leq j \lt i$$$ .

We have 2 types of $$$dp$$$ transition , here $$$j$$$ is the position where previous operation was applied just before operation on $$$i$$$ .

1) For all $$$i-k+1 \leq j \lt l$$$

$$$dp[i] = max (dp[i],dp[j]-sum(i,j+k-1)+sum(i,i+k-1))$$$

Elements from $$$j$$$ to $$$j+k-1$$$ and $$$i$$$ to $$$i+k-1$$$ have become $$$zero$$$ .

But since , Elements from $$$i$$$ to $$$j+k-1$$$ will be counted twice so we subtract them .

2) For all $$$0 \leq j \lt min(i-k+1,l)$$$

$$$dp[i] = max (dp[i],dp[j] + sum(i,i+k-1))$$$

Type 2 transitions can simply be handled by maintaining array whose $$$p$$$ $$$th$$$ index will store maximum value of $$$dp[j]$$$ for all $$$0 \leq j \leq p$$$.

For type 1 transition you can iterate each $$$j$$$ and maximize the value accordingly. But that will give us solution with time complexity of $$$O(n*k)$$$. Which is not acceptable for this problem.

Note that

$$$dp[j] - sum(i,j+k-1) + sum(i,i+k-1) = dp[j] - (p[j+k-1] - p[i-1]) + (p[i+k-1] - p[i-1])$$$
$$$= dp[j] - p[j+k-1] + p[i+k-1] $$$

This means that if we somehow get the maximum value of $$$dp[j] - p[j+k-1]$$$ for $$$i-k+1 \leq j \lt l$$$ , then we can get the desired transition by simply adding $$$p[i+k-1]$$$ to that maximum value.
Maximum value in a range can be calculated by maintaining a segment tree with range query for finding maximum and point update. For update we need to update the value at $$$i$$$ $$$th$$$ position of segment tree with value $$$dp[i] - p[i+k-1]$$$ after we calculate the value of $$$dp[i]$$$.

Our answer will be $$$(Total sum$$$ — $$$max(dp[i]))$$$
Time Complexity is $$$O(n log n)$$$

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

struct Seg      
{
    ll def=-(ll)1e18; 
    int n,sz=1;
    vector<ll> v;
    ll comb(ll l,ll r)
    {   
        ll res=max(l,r);
        return res;
    }
    void build(int s)
    {
        n=s;
        while(sz<n)
            sz*=2;
        v.resize(2*sz,def);
    }
    ll get(int l,int r)
    {
        ll l1=def,r1=def;
        for(l+=sz,r+=sz; l<r; l>>=1,r>>=1)
        {
            if(l&1)
                l1=comb(l1,v[l++]);
            if(r&1)
                r1=comb(v[--r],r1);
        }
        ll res=comb(l1,r1);
        return res;
    }
    void set(int i,ll a)
    {
        i+=sz;
        v[i]=a;
        while(i>1)
        {
            i>>=1;
            v[i]=comb(v[2*i],v[2*i+1]);
        }
    }   
};

void Solve()    
{
    int n,k;
    string s;
    cin>>n>>k>>s;
    vector<int> id(n+1,-1);// l for each position
    vector<ll> p(n+1);//prefix sum
    for(int i=1; i<=n; i++)
    {
        cin>>p[i];
        p[i]+=p[i-1];
        if(s[i-1]=='1')
            id[i]=i-1;
        else  
            id[i]=id[i-1];
    }
    vector<ll> dp(n+1),mx(n+1);
    Seg ss;
    ss.build(n+1);
    for(int i=1; i<=n; i++) 
    {
        ll val=p[min(n,i+k-1)];
        if(id[i]>=0)
        {
            dp[i]=max(val-p[i-1],val+ss.get(max(1,i-k+1),id[i]+1));
            if(min(i-k,id[i])>0)
                dp[i]=max(dp[i],val+mx[min(i-k,id[i])]-p[i-1]);
            ss.set(i,dp[i]-val);
        }
        mx[i]=max(mx[i-1],dp[i]);
    }
    cout<<p[n]-mx[n];
}
int main()                                                                                                                    
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    while (t--) 
        Solve();
    return 0;
}