Author : Thakur Emon
This problem can be solved by segment tree. when a player played his turn he hands over one half of the array to another player. As a result each time the array size is reduced by half. So, we can say that there will be at most \(logN\) turns in a game which is suitable for segment tree.

The segment tree will store two results {x,y} (x: if the current player is Thakur. y: if the current player is Roy). the transition from child to parent node will be

\(sg[parent].thakur = min(sg[child_1].roy , sg[child_2].roy);\)
\(sg[parent].roy = max(sg[child_1].thakur , sg[child_2].thakur);\)

it works because when its Thakurs turn he will divide the array into two part and will guess which part will give the minimum when roy plays with that part and vice versa.

update operation also works in \(logN\) because when an element of one half is updated it does not effect on the other half.

the root of the segment tree will contain answer for both Thakur and Roy.
complexity : \(O(NlogN)\)

**note: calculate the mid value carefully **

#include<bits/stdc++.h>
using namespace std;
int a[200005];
pair<int,int> sg[800005];
void build(int node,int start,int end)
{
    if(start==end)
    {
        sg[node] = {a[start],a[start]};
        return;
    }
    int mid = (start + end-1)/2;
    build(node*2,start,mid);
    build(node*2+1,mid+1,end);
    sg[node].first = min(sg[node*2].second,sg[node*2+1].second);
    sg[node].second = max(sg[node*2].first,sg[node*2+1].first);
    
}

void update(int node,int start,int end,int ind,int val)
{
    if(start==end)
    {
        sg[node] = {val,val};
        a[ind] = val;
        return;
    }
    int mid = (start+end-1)/2;
    if(ind <= mid) update(node*2,start,mid,ind,val);
    else update(node*2+1,mid+1,end,ind,val);
    sg[node].first = min(sg[node*2].second,sg[node*2+1].second);
    sg[node].second = max(sg[node*2].first,sg[node*2+1].first);
}

int main()
{
    int n,q; cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,1,n);
    while(q--)
    {
        int ind,val,player;
        cin >> ind >> val >> player;
        update(1,1,n,ind,val);
        (player)? cout<<sg[1].second<<'\n': cout<<sg[1].first<<'\n';
    }
}