# TOURQUE - EDITORIAL

Contest

Practice

Setter: Gaurish Baliga

Tester: Rohit Tawde

Editorialist: Gaurish Baliga

Easy-Medium

Trees.

# PROBLEM

Krakenmonstor decided to host a supertournament. 2^N people are playing the tournament. Each player has a strength S associated with them.

You are given the initial strength array S where S{_i} denotes the strength of the i^{th} and are required to process Q queries. The queries are of 3 types:

• 1 X : Print ‘YES’ if player X is the current winner of the tournament, otherwise print ‘NO’.

• 2 X W: Update the strength of the X^{th} player to W. Note that the results of the tournament might change after this update.

• 3 A B: If player A has won more matches than player B print ‘FIRST’, else if B has won more matches print ‘SECOND’, else print ‘DRAW’.

# EXPLANATION

As the problem suggests, we need to maintain a Tree data structure to handle these queries. Since the Tree happens to be a perfect binary tree, we can handle each query in O(logn) for an overall time complexity of O(nlogn).

Now for implemention, we know that if a tree were to be flattened in an array, then

children of a[i] would be a[2i] and a[2i + 1]. We use exactly this to maintain our Tournament Tree

For Query 1, a[1] would hold the winner of the tournament

For Query 2, if we update a[i], then updating all other nodes could just be done by halfing i everytime

For Query 3, we can maintain another win array which denotes how many games a particular person has won

O(N\log (N)).

# SOLUTION

Setter's Solution
``````
#include<bits/stdc++.h>

using namespace std;

int main()

{

int n, q; cin >> n >> q;

vector<pair<int,int> >arr((2<<n) + 1);

vector<int>win((1<<n) + 1);

for(int i = (1<<n) ; i < (2<<n); i++)

{

cin >> arr[i].first;

arr[i].second = (i - (1<<n) + 1);

}

for(int i = (1 << n) - 1; i >= 1; i--)

{

arr[i] = max(arr[2*i], arr[2*i + 1]);

win[arr[i].second]++;

}

for(int i = 0; i < q; i++)

{

int type; cin >> type;

if(type == 1)

{

int x; cin >> x;

cout << (x == arr[1].second ? "YES\n" : "NO\n");

}

if(type == 2)

{

int ind, val; cin >> ind >> val;

arr[(1<<n) + ind - 1] = make_pair(val, ind);

for(int i = ((1<<n) + ind - 1)/2; i >= 1; i /= 2)

{

if(arr[i].first != max(arr[2*i].first, arr[2*i + 1].first))

{

win[arr[i].second]--;

arr[i] = max(arr[2*i], arr[2*i + 1]);

win[arr[i].second]++;

}

}

}

if(type == 3)

{

int a, b; cin >> a >> b;

if(win[a] > win[b]) cout << "FIRST\n";

else if(win[b] > win[a]) cout << "SECOND\n";

else cout << "DRAW\n";

}

}

}

``````
Tester's Solution
``````
#include<bits/stdc++.h>

#define ll long long

#define pb push_back

#define F first

#define S second

#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

using namespace std;

int build(vector<int>&v, int i){

if(v[i]!=-1){

return v[i];

}

v[i]=max(build(v,(2*i)+1),build(v,(2*i)+2));

return v[i];

}

void check(vector<int>&v,int i, int k, int &c){

if(v[i]==k)

c++;

else

return;

if(i==0)

return;

else{

int ii=(i-1)/2;

check(v, ii, k, c);

}

}

void update(vector<int>&v,int i){

v[i]=max(v[(2*i)+1],v[(2*i)+2]);

if(i==0)

return;

else{

int ii=(i-1)/2;

update(v, ii);

}

}

int main() {

fast_io;

int t;

t=1;

while(t--){

ll n,q;

cin>>n>>q;

ll n1=pow(2,n);

vector<int>v;

while(n1){

for(int i =0;i<n1;i++){

v.pb(-1);

}

n1/=2;

}

n=pow(2,n);

vector<int>a(n);

for(int i =0; i <n;i++){

cin>>a[i];

}

reverse(a.begin(),a.end());

for(int i =0; i <n;i++){

v[i]=a[i];

}

map<ll,ll>pos;

reverse(v.begin(),v.end());

build(v,0);

for(int i =0;i<v.size();i++){

pos[v[i]]=i;

}

ll p=v.size()-n-1;

for(int i =0;i<q;i++){

ll k;

cin>>k;

ll x,y;

cin>>x;

if(k==3){

cin>>y;

ll k1=v[p+x];

ll k2=v[p+y];

int c1=0,c2=0;

check(v, p+x, k1, c1);

check(v, p+y, k2, c2);

if(c1>c2){

cout<<"FIRST\n";

}

else if(c2>c1){

cout<<"SECOND\n";

}

else{

cout<<"DRAW\n";

}

}

else if(k==2){

cin>>y;

pos[v[p+x]]=0;

v[p+x]=y;

pos[y]=p+x;

ll ii=(p+x-1)/2;

if(ii)

update(v, ii);

}

else{

if(v[0]==v[p+x]){

cout<<"YES\n";

}

else{

cout<<"NO\n";

}

}

}

}

return 0;

}

``````

[/details]