美团春招笔试

前面选择写太久了（半小时，那些词汇既熟悉又陌生，我企图回忆出些什么），导致最后一题没敲完，下次还是先去写编程题吧。三道编程题目测都是橙题（中等偏下），第三题代码量大些

选择题大模型不会算法题第二题一直超时，卡在百分之四十的通过率，后面试着光输入并打印常数也超时最后十分钟灵机一动换成 c++ 过了第三题直接跳了

往年笔试合集：2023春招秋招笔试合集2024春招秋招笔试合集笔试时间：2026年3月14日第1题 - 小美的因子数量题目小美很喜欢因子数量为奇数的数。现在小芳给了小美一个区间 ，请你帮小美算出区间内有多少个因子数量为奇数的数。【名词解释】因子：对于正整数 ，如果存在正整数 使得 能被 整除，则称 是 的因子。例如， 的因子有 。输入描述第一行输入两个整数 （），表示询问的区间。输出描述输出一个整数，表示区间内因子数量为奇数的数的个数。样例输入1 1 1 样例输出1 1 样例说明1在这个样例中，区间内唯一可以取到的数字为 ，其因子数量只有自身，为奇数。样例输入2 4 5 样例输出2 1 样例说...

出题人真疯了？？？？？笔试题又出数据结构，上次默写HLD这次默写主席树是吧？？？？t1贪心，t2dp，都算简单题吧，写的很顺。t3 求一个数组有多少子区间，使得区间端点和大于区间最大值，n1e5，值域1e6，262mb！！！！！！！考虑在笛卡尔树上做，那么就是在每个节点上求有多少跨越最大值的区间且区间端点的和大于最大值一个做法是考虑这个最大值把区间分成两部分，枚举小的那部分，设枚举到的为x，查询大的那部分有多少满足值大于max-x，这个显然可以直接上主席树做，枚举的复杂度于在笛卡尔树上枚举小的子树（其实不太等价，但是差不多就是这个意思），复杂度等于树上启发式合并，总体时间O(nlog^2),空间O(nlogn)然后坑点来了，首先上面那个枚举其实有一点conner case，不太好写，其次这个空间其实是开不下1e6的主席树的，你需要完全动态开点，初始树都不建来卡一下常，或者写离散化赛时被卡mle了，没调完。贵司是真的只招火箭毛毛虫高手吗？？？？upd：和队友聊了下，队友说可以先递归大子树，在再这个节点上做操作，这样就不需要做主席树的复杂操作了，可以直接上普通线段树/树状数组或者pbds::tree，不会mle