Heh, there are at least two problems with this approach. The first is that you need to explicitly make every Collection conform to LastIndex. The second is that if your generic collection conditionally conforms to BidirectionalCollection, you'll get the O(N) implementation unconditionally from a generic context.
It would be nice if we had a mechanism for extending protocols with additional dispatched requirements.
+1; we had a pitch on these forums for such a feature recently but I can't find it.