Well, O(1) is a bit much to ask but O(y-x+l-k) is quite possible :) That's the classic application for a hash:

First, transform your first slice to the keys of a hash while doing the incrementing:

Then your result list is the result of a grep on those elements that exist in the hash:

@result = grep { exists $h{$_} } @a[$k .. $l];
say join ', ', @result;
[download]