想整一道题折磨折磨学弟学妹,之后想了个加强版准备迫害同机房不会平衡树还天天不务正业刷水题的同学
大意:给定长度为 n 的非负整数数列 (不保证无重复元素) 以及 q 次操作,操作为以下两种之一:
1 x :查询数列中不超过最大回文数的最大非回文数,将其输出并删除 x 个;若该数个数小于 x
,忽略多余的删除次数;若找不到指定的回文数 / 非回文数 ,输出 −1 并在数列中插入 x ;
2 x :查询对象改为数列中不小于最小非回文数的回文数,其余相同;
1≤n≤4×106,1≤q≤3×106,0≤x≤2×104 。
保证所有输入的数不超过 1018 。
解法很显然,就不再说明了......上面的平衡树已经给提示了。
这边想把主席树卡掉,因为一名同学正在学,但是不太确定能不能卡掉?(没写过主席树)
如果不能卡掉的话,这边最后才会考虑卡内存(虽然某种意义上没卵用......主席树可以优化空间),另一思路是把回文数改成质数,不过这样更那啥了......