0x3f

字符串哈希,是一种能将字符串映射成非负整数的算法. 一般使用BKDR Hash进行哈希计算. 具体做法是,将字符串看作一个 $b$ 进制的数字,计算它在十

可以发现,当第 $ i $ 个订单可以满足时,第 $ i-1 $ 个订单也可以满足. 于是可以想到二分答案求解,差分计算每个订单,复杂度 $ O(n\log{n}) $ . #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long num[1000006];

$ O(n) $ 做法 首先预处理一个数组res[i],表示第 $ 1 $ 到 $ i $ 的客栈中编号最大且满足最低消费小于等于q的客栈编号; 维护一个前缀和数组ans[

前缀和 作用:求区间和 时间复杂度: $ O(n) $ 预处理, $ O(1) $ 查询. 预处理 假设原数组为$ a_1,a_2,a_3,… $ 前缀和数组 $ sum_1=a_1 $ $ sum_2=a_1+a_2=sum_1+a_2 $ $ sum_3=a_1+a_2+a_3=sum_2+a_3 $ $ … $ 查询 查询 $ [l,r] $ 区间内和：

前提条件-满足单调性 满足单调性: ✅✅✅✅✅✅❌❌❌❌ (求最大值) ❌❌❌✅✅✅✅✅✅✅ (求最小值) 不满足单调性: ✅❌✅✅✅❌ (建议直接暴力) 求