这类 \(O(\log V)\) 的 trick，都是利用了值变化单调且变化幅度大的特性
每次下降或上升都跨越一个“数量级”，因此变化次数有限，即使包在循环中整体也只会是 \(O(n \log V)\) 而非 \(O(n^2)\)。
下面举几个比较典型的例题
GCD问题
gcd为1的最小区间
https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1
主要思路：
利用一个 vector<pair<int,int>> p 来维护状态，对于每个新加入的数值，遍历当前 p 中的所有元素，计算它们与 nums[i]的最大公约数，得到所有以 i 结尾的子数组的 GCD
如果新得到的 GCD 与上一个相同，则说明这两个区间可以合并，只需要更新右端点即可；如果不同（变小），则说明出现了一个新的 GCD 段，将其追加到 p 的末尾。
通过这种方式，p 中的每个元素 {g, r} 实际上表示：所有以当前位置结尾、GCD 值为 g 的子数组，其起点区间的右端为 r；当出现 g = 1 时，我们即可通过 r 快速确定包含 GCD 为 1 的最短子数组长度。
表面上看，每次遍历都要处理整个 p，似乎复杂度是 \(O(n^2)\)，但实际上 p 的长度非常有限。因为随着遍历的进行，子数组的 GCD 值只会不增。当它下降时，必然降到某个约数，因此每次下降至少减半。由此可知，对于任意位置，GCD 值最多下降 \(\log_2 V\) 次（其中 V 为数组中的最大元素），即 p 的长度在任意时刻都不会超过 \(O(\log V)\)。因此整个算法的时间复杂度是 \(O(n \log V)\)，空间复杂度也是 \(O(\log V)\)。
给出下面代码：
int len=n;
vector<pair<int,int>>q;
for(int i=0;i<n;i++){q.push_back({nums[i],i});int j=0;for(auto& item:q){// 遍历已有数据item.first=gcd(item.first,nums[i]);if(j>0 && q[j-1].first==item.first)q[j-1].second=item.second;// 相同 GCD 更新右端点else q[j++]=item; // 不同 GCD 添加 }if(q[0].first==1)len=min(len,i-q[0].second+1);q.resize(j);// for(auto& item:q)cerr<<item.first<<' '<<item.second<<nl;// cerr<<len<<nl;
}
最大公因数等于 k 的子数组数目
https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k
思路与上面一致，还是每次相同就记录可选的最右端点，不过添加了一个左端点来记录长度
答案统计可以这么想，只要添加 nums[i] 符合条件，原来长度为 len，那么新增的符合条件的子数组就是 len 个 ，即每个数与nums[i]组合一下。
int subarrayGCD(vector<int>& nums, int k) {int n=nums.size();vector<array<int,3>>q;int res=0;for(int i=0;i<n;i++){int j=0;q.push_back({nums[i],i,i});for(auto&[w,l,r]:q){w = gcd(w,nums[i]);if(j>0 && w==q[j-1][0])q[j-1][2]=r;else{q[j++]={w,l,r};}}q.resize(j);// cerr<<"i="<<i<<":"<<nl<<" ";for(auto&[w,l,r]:q){// cerr<<w<<" "<<l<<" "<<r<<nl;if(w==k)res+=r-l+1;}// cerr<<nl;}return res;
}
LCM问题
最小公倍数等于 k 的子数组数目
https://leetcode.cn/problems/number-of-subarrays-with-lcm-equal-to-k
主要思路：和上面GCD问题一模一样，只是把 GCD 变为了 LCM
int subarrayLCM(vector<int>& nums, int k) {int n=nums.size();vector<array<int,3>>q;int res=0;for(int i=0;i<n;i++){int j=0;q.push_back({nums[i],i,i});for(auto&[w,l,r]:q){w = lcm(w,nums[i]);if(w>k)continue;if(j>0 && w==q[j-1][0])q[j-1][2]=r;else{q[j++]={w,l,r};}}q.resize(j);// cerr<<"i="<<i<<":"<<nl<<" ";for(auto&[w,l,r]:q){// cerr<<w<<" "<<l<<" "<<r<<nl;if(w==k)res+=r-l+1;}// cerr<<nl;}return res;
}
AND问题
子数组and等于k的数量
https://leetcode.cn/problems/number-of-subarrays-with-and-value-of-k
long long countSubarrays(vector<int>& nums, int k) {int n=nums.size();vector<array<int,3>>q;long long res=0;for(int i=0;i<n;i++){q.push_back({nums[i],i,i});int j=0;for(auto &[w,l,r]:q){w&=nums[i];if(j>0 && q[j-1][0]==w)q[j-1][2]=r;else q[j++]={w,l,r};}q.resize(j);for(auto &[w,l,r]:q){if(w==k)res+=r-l+1;}}return res;
}
OR问题
子区间or值与给定值k的最小绝对值
https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/description/
给定一个数组 nums 和 一个正整数 k
一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。
int minimumDifference(vector<int>& nums, int k) {int n=nums.size();vector<int>buk;int res=2e9;for(int i=0;i<n;i++){buk.push_back(nums[i]);int j=0;for(auto x:buk){int mid=x|nums[i];if(!j || mid!=buk[j-1])buk[j++]=mid;}buk.resize(j);for(auto x:buk){res=min(res,abs(x-k));}}return res;
}
所有子区间or值的种类数
https://leetcode.cn/problems/bitwise-ors-of-subarrays
int subarrayBitwiseORs(vector<int>& nums) {int n=nums.size();vector<int>q;set<int>res;for(int i=0;i<n;i++){int j=0;q.push_back(nums[i]);for(auto& w:q){w=w|nums[i];if(!j || w!=q[j-1])q[j++]=w;}q.resize(j);res.insert(q.begin(),q.end());}return res.size();
}
待续 其他相关的，待我先做完 ...