z-names

Can someone give me idea for solving this task:
http://z-trening.com/tasks.php?show_task=5000000444

Offline idea:
Sort all names with their positions.
And for i-th element in sorted array find how many elements before it has position smaller than it's.

Online idea:
Use Trie with some dynamic programming...

use fenwick tree