Simple balanced trees with O(1) concat?
You can trivially make a data structure with O(1) amortized concatenation time, by just reinserting everything from one tree on the other on concatenation (which has O(n log n) cost, exactly the same as was used in constructing that tree in the first place, so the overall time is still O(n log n)), but this is cheating.

For worst-case O(1) time, the authors claim it was an open problem for any data structure, so I don't think you're going to find an easy answer.