逗逼分块,写完题解结果被吞QoQ.直接贴代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
typedef long long LL;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*fS=buf,*fT=buf;
        if(fS==fT){fT=(fS=buf)+fread(buf,1,L,stdin);if(fS==fT)return EOF;}
        return*fS++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[600010],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 100010
int begin[510],end[510],bel[N];
 
double res[N];
 
struct Stack{
    int top;
    double s[510];
    Stack():top(0){}
    inline void upd(int l,int r){
        top=0;
        for(int i=l;i<=r;++i)if(!top||res[i]>s[top])s[++top]=res[i];
    }
    inline int getans(const f2&x){
        if(!top||s[top]<=x)return 0;
        int L=1,R=top,mid;
        while(L<R){
            mid=(L+R)>>1;
            if(s[mid]>x)R=mid;else L=mid+1;
        }return top-L+1;
    }
}S[510];
 
int main(){
    int n,m;Fio::Get(n),Fio::Get(m);register int i,j;
 
    int persize=sqrt(n),nums=0;
    for(i=1;i*persize<=n;++i)begin[++nums]=(i-1)*persize+1,end[nums]=i*persize;
    if(n%persize)++nums,begin[nums]=(nums-1)*persize+1,end[nums]=n;
    for(i=1;i<=nums;++i)for(j=begin[i];j<=end[i];++j)bel[j]=i;
 
    for(i=1;i<=n;++i)res[i]=0;
 
    int x,y,ret;f2 Max;
    while(m--){
        Fio::Get(x),Fio::Get(y);
        res[x]=(f2)y/x;
        S[bel[x]].upd(begin[bel[x]],end[bel[x]]);
        for(ret=0,Max=0,i=1;i<=nums;++i){
            ret+=S[i].getans(Max);
            if(S[i].top&&S[i].s[S[i].top]>Max)Max=S[i].s[S[i].top];
        }
        Fio::print(ret);
    }
 
    return Fio::final(),0;
}

思路:

首先若\(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;
}