BZOJ3834:[Poi2014]Solar Panels 分块

思路:

首先若\(x\)可以作为答案,必定满足\(b/i-(a-1)/i\geq{1},d/i-(c-1)/i\geq{1}\).

注意到单独的\(v/i\)是只有\(O(\sqrt{n})\)块的,我们可以单独算出对于\(a,b\)满足条件的块,以及对于\(c,d\)满足条件的块.

接下来我们只需求出 两部分的最大交点即可,我们可以在\(O(\sqrt{n})\)的时间内线性扫描得到.

#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
int l[2][100000],r[2][100000],blks[2];
int main(){
    int T;cin>>T;int a,b,c,d,last,ans;register int i,j,k;
    while(T--){
        scanf("%d%d%d%d",&a,&b,&c,&d);blks[0]=blks[1]=0;
        for(i=1;i<a;i=last+1){
            last=min(b/(b/i),(a-1)/((a-1)/i));
            if(b/i-(a-1)/i>=1)l[0][++blks[0]]=i,r[0][blks[0]]=last;
        }
        l[0][++blks[0]]=a,r[0][blks[0]]=b;
        for(i=1;i<c;i=last+1){
            last=min(d/(d/i),(c-1)/((c-1)/i));
            if(d/i-(c-1)/i>=1)l[1][++blks[1]]=i,r[1][blks[1]]=last;
        }
        l[1][++blks[1]]=c,r[1][blks[1]]=d,
        j=1;
        for(ans=0,i=1;i<=blks[0];++i){
            while(j<=blks[1]&&r[1][j]<l[0][i])++j;
            for(k=j;k<=blks[1]&&l[1][k]<=r[0][i];++k)ans=max(ans,min(r[0][i],r[1][k]));
        }
        printf("%d\n",ans);
    }return 0;
}