這類 \(O(\log V)\)
每次下降或上升都跨越一個“數量級”，因此變化次數有限，即使包在循環中整體也只會是 \(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();
}待續 其他相關的，待我先做完 ...