Chuyên đề chặt nhị phân Bài 1:

include<bits/stdc++.h>

using namespace std; int a[100000],q,n; int chatmax(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>d) r=mid-1; else l=mid+1,ans=mid; } return(ans); } int chatmin(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>=d) r=mid-1,ans=mid; else l=mid+1; } return(ans); } int main(){ freopen("bustatq.inp","r",stdin); freopen("bustatq.out","w",stdout); cin>>n>>q; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=q;i++){ int l,r; cin>>l>>r; if (l>a[n]) cout<<"0"<<endl; else cout<<chatmax(r)-chatmin(l)+1<<endl; } } Bài 2:</p>

include<bits/stdc++.h>

define ll long long int

using namespace std; ll n,a[1000000],kt[1000000],f[1000000],q; ll chatmin(ll x){ ll l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>=x) r=mid-1,ans=mid; else if (a[mid]<x) l=mid+1; } return(ans); } ll chatmax(ll x){ ll l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>x) r=mid-1; else if (a[mid]<=x) l=mid+1,ans=mid; } return(ans); } int main(){ unordered_map<ll,ll> mp; cin>>n>>q; for (int i=1;i<=n;i++){ cin>>a[i];mp[a[i]]++; } sort(a+1,a+n+1); if (mp[1]>0) kt[1]=1; ll j=1; for (int i=1;i<=34;i++) { j=2; if (mp[j]>0) kt[j]=1; } j=1; for (int i=1;i<=27;i++) { j=3; if (mp[j]>0) kt[j]=1; } j=1; for (int i=1;i<=25;i++) { j*=5; if (mp[j]>0) kt[j]=1; } f[0]=0;a[0]=0; for (int i=1;i<=n;i++){ f[i]=f[i-1]; if (kt[a[i]]==1) f[i]++; } for (int i=1;i<=q;i++){ ll z,x; cin>>z>>x; if (z>a[n]) cout<<"0"<<endl; else { int k=chatmin(z); int k1=chatmax(x); cout<<f[k1]-f[k-1]<<endl; } } } Bài 3:</p>

include<bits/stdc++.h>

using namespace std; int a[100000],b[100000],c[100000],n; int chatmax(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>d) r=mid-1; else l=mid+1; if (a[mid]==d) ans=mid; } return(ans); } int chatmin(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>=d) r=mid-1; else l=mid+1; if (a[mid]==d) ans=mid; } return(ans); } int main(){ cin>>n; for (int i=1;i<=n;i++) cin>>a[i],a[i]=a[i]a[i]; for (int i=1;i<=n;i++) cin>>b[i],b[i]=b[i]b[i]; for (int i=1;i<=n;i++) cin>>c[i],c[i]=c[i]*c[i]; sort(a+1,a+n+1);int res=0; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ int k=chatmax(b[i]+c[j]); int k1=chatmin(b[i]+c[j]); if (k1>0) res=res+k1-k+1; int z=chatmax(abs(b[i]-c[j])); int z1=chatmin(abs(b[i]-c[j])); if (z1>0) res=res+z1-z+1; } } cout<<res; } Bài 4:</p>

include<bits/stdc++.h>

using namespace std; long long check(long long k){ long long a=k/3; long long b=k/5; long long c=k/15; return(k-(a+b-c)); } int main(){ freopen("COUNTGAM.inp","r",stdin); freopen("COUNTGAM.out","w",stdout); long long n; cin>>n; long long ans=0; long long l=1,r=1e14; while (l<r){ long long mid=(l+r)/2; if (check(mid)<n) l=mid+1; if (check(mid)>=n) r=mid,ans=mid; } cout<<ans; }</p>