统计满足条件区间数量问题
思路:双指针/二分,固定某一端点统计合法的另一端点数量从而计数
难点:边界条件
二分
易错点:
固定左端点后两次二分,一定注意不能轻易像“数的范围那样”在第二次二分前只初始化r
对于这道题,是因为不一定存在等于k的数,导致l可能左移
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define y1 y__
#define time t__
#define lowbit(x) ((x)&(-x))
const int N=2e5+10;
int T;
int k,n;
int s2[N],s5[N];
int main(){
speed_up;
cin>>T;
while(T--){
cin>>n>>k;
for(int i=1;i<=n;i++){
int x;
s2[i]=s5[i]=0;
cin>>x;
while(x%2==0)x/=2,s2[i]++;
while(x%5==0)x/=5,s5[i]++;
s2[i]+=s2[i-1];
s5[i]+=s5[i-1];
}
ll ans=0;
for(int i=1;i<=n;i++){
if(min(s5[i]-s5[i-1],s2[i]-s2[i-1])>k)continue;
int l=i,r=n+1;
while(l<r){
int mid=l+r>>1;
if(min(s5[mid]-s5[i-1],s2[mid]-s2[i-1])>=k)r=mid;
else l=mid+1;
}
int L=l;
if(L==n+1)continue;
l--,r=n;
while(l<r){
int mid=l+r+1>>1;
if(min(s5[mid]-s5[i-1],s2[mid]-s2[i-1])<=k)l=mid;
else r=mid-1;
}
int R=r;
ans+=R-L+1;
}
cout<<ans<<'\n';
}
return 0;
}
双指针
易错点:
注意st,ed的作用范围,一定注意当存在循环中continue时,严防st/ed“掉队”,即当小于i时更新回i
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define y1 y__
#define time t__
#define lowbit(x) ((x)&(-x))
const int N=2e5+10;
int T;
int k,n;
int s2[N],s5[N];
int main(){
speed_up;
cin>>T;
while(T--){
cin>>n>>k;
for(int i=1;i<=n;i++){
int x;
s2[i]=s5[i]=0;
cin>>x;
while(x%2==0)x/=2,s2[i]++;
while(x%5==0)x/=5,s5[i]++;
s2[i]+=s2[i-1];
s5[i]+=s5[i-1];
}
ll ans=0;
int st=1,ed=1;
for(int i=1;i<=n;i++){
if(min(s5[i]-s5[i-1],s2[i]-s2[i-1])>k)continue;
if(st<i)st=i;
while(st<=n){
if(min(s5[st]-s5[i-1],s2[st]-s2[i-1])<k)st++;
else break;
}
if(st==n+1)break;
if(ed<i)ed=i;
while(ed<=n){
if(min(s5[ed]-s5[i-1],s2[ed]-s2[i-1])<=k)ed++;
else break;
}
ans+=ed-st;
}
cout<<ans<<'\n';
}
return 0;
}