It's possible to do AND and NOT searches in
genres - green column AND, red column NOT
and categories - no prefix AND, '-' prefix NOT
Naturally, we need OR operator. Perhaps, it isn't useful for genres search (easy to exclude everything unnecessary with such small number of choices). But with large number of categories OR is necessary.

Proposal. In advanced search categories input box:

• prefix means AND

• prefix means NOT
  no prefix means OR

Last thing is priority/brackets rules, but i can't think of a way to implement it in existing one-tag-per-line model. Anyway, we can live without it.