Advanced search multi-select logical conditions

I have a client that wants to be able to control the logic expression on a multi-select search on a custom field. When selecting multiple values, in sometimes she wants the condition to be “or” between the selected values and other times she want an “and” condition.

For example, if you had listings of vacation resort site with 2 custom fields: city & unique features. If a visitor selects 2 cities and 2 unique features she wants to see all listings for either city that have both features. That means the search on the city is an “or” condition but the search the unique feature is an “and” condition (return all listings that have a city of “A” or “B” and have unique feature “C” and “D”).

Can this be done with the existing theme or will this require an enhancement?