Each line is added exactly once and removed at most once. That's O(n) add operations, O(n) 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 O(n). Querying: Same logic.
Each front-pop happens at most once per line. Total query overhead: O(n). Combined: O(n) time for n states. Your O(n2) DP becomes O(n) because we do O(n) work total, not O(n) work per state. That's the power of CHT.