暴力即可。
暴力跳肯定是对的,因为集合 SSS 中最多就 q−1000q-1000q−1000 个数,所以复杂度最坏 O(1000q)\mathcal{O}(1000q)O(1000q)。
实际上暴力就是对的(加上记忆化)!
考虑只有加数没有删除数字,那么对于一个固定的 kkk,这个 ttt 肯定是不降的,于是每次记忆化即可。
考虑这个算法的最坏复杂度,最坏情况下肯定是先加入 1,2,...,q1,2,...,q1,2,...,q,然后询问 1,2,...q1,2,...q1,2,...q,这个复杂度是调和级数级别的,所以复杂度就是 O(qlogq)\mathcal{O}(q\log q)O(qlogq)。
使用您的 Hydro 通用账户