Each line is added exactly once and removed at most once. That's add operations, remove operations. Adding: You might pop multiple lines when adding one, but total pops across all adds is bounded by total lines ever added. That's . Querying: Same logic.
Each front-pop happens at most once per line. Total query overhead: . Combined: time for states. Your DP becomes because we do work total, not work per state. That's the power of CHT.