First hint

Try solving this problem (Codeforces) first.

Second hint

You will need four “segment trees” rather than the two you used for the linked problem, for:

• boarding an eastbound train
• getting off an eastbound train
• boarding a westbound train
• getting off a westbound train

Example for “boarding an eastbound train”. “Getting off a westbound train” would be similar but with the edges reversed.

Example for “getting off an eastbound train”. “Boarding a westbound train” would be similar but with the edges reversed.

Once you have the segment trees in place you can use extra nodes for each train, so that you add \(O(\log N)\) edges each train, something like this for a train going from \([1, 2]\) to \([4, 6]\):