Can anyone tell me how to solve this problem using segment tree

1
2

You don’t need to!

Your hint should be that it does not ask for any “Range Query”, there are just updates. You only need to answer once at the end.

You can use a set, that contains all the participants currently in the tournament.
Then for every query, search for ‘L’ in the set, and continue erasing elements till ‘R’, except ‘X’.
Assign the winner of everyone who lost this round as ‘X’.
Now since you’ll only erase at most N-1 times, the complexity is just O(NlogN).

int main()
{	
  int n,m;
  cin>>n>>m;
  set<int> S;
  vector<int> P(n+1);
  
  for(int i=1;i<=n;i++) S.insert(i); // Knights Alive.
  while(m--)
  {
	int l,r,x;
	cin>>l>>r>>x;
	auto y=S.lower_bound(l);  //Find the first Knight to erase.
	vector<int> toerase;
	while(y!=S.end()) 
	{
		if(*y>r) break;
		if(*y!=x)
		{
			P[*y]=x;
			toerase.push_back(*y);
		}
		y++;
	}
	for(auto xx:toerase) S.erase(xx);   //Erase the Knights from the set.
  }
  for(int i=1;i<=n;i++) cout<<P[i]<<" ";
  cout<<endl;
}
1 Like