题解：AT_code_formula_2014_final_h 平和協定

· · 题解

把一个国家看成平面直角坐标系里的一个点，坐标为 (a_i,b_i)，一对点合法当且仅当两个点分别为左下角和右上角，且以这两个点为左下角和右上角的长方形的面积在 [S1,S2] 之间。

下面假设 n 和值域同阶。

首先枚举一个点 (x,y)，考虑对于长方形的宽（即横坐标之差）整除分块。整除分块后相当于查询一个矩形中有多少个点。

把询问存下来，按横坐标排序，扫描线。因为有 O(n\sqrt n) 次询问，但是只有 O(n) 次修改，于是可以用一个 O(\sqrt n) 修改、O(1) 查询的分块来做。

总的时间复杂度是 O(n\sqrt n)。

注意到题目的空间限制只有 64MB，比较卡空间。

可以一边进行询问一边整除分块。具体来说，假设点 i 的整除分块进行到了 [l,r]，可以先不把点 i 之后的询问存储下来，而是等到询问完 r 以后才获取下一个询问。每次扫描线做完 x=p 以后，把存储横坐标为 p 询问的 vector 清空。可以用 shrink_to_fit() 来清空空间。

这样子，可以做到时间复杂度 O(n\sqrt n)，空间复杂度 O(n)。

但是实际运行，由于整除分块的大常数，以及频繁地进行 vector 的操作，所以跑得并没有多快。

const int V=50000,N=V+99,B=250;
int n,s1,s2,belong[N]={},tag[N]={},pre[N]={},cnt[N]={},l[N<<1]={};
pair<int,int> a[N]={};
struct Ask { int l,r,from; bool t; };
vector<Ask> ask[N]={},now;
int main()
{
    // usefile("peace");
    int i,p,j,maxy=0,maxx=0; ll ans=0;
    read(n,s1,s2);
    for(i=1;i<=n;++i) {
        read(a[i].first,a[i].second);
        maxx=max(maxx,a[i].first);
        maxy=max(maxy,a[i].second);
    }
    sort(a+1,a+1+n);
    for(i=1;i<=maxy;++i)
        belong[i]=i/B+1;
    auto push=[&](int xl,int xr,int yl,int yr,int t)->void {
        if(xl>xr) return ;
        yr=min(yr,maxy);
        if(xl>xr) return ;
        ask[xl-1].push_back((Ask){yl-1,yr,t,!(t&1)});
        ask[xr].push_back((Ask){yl-1,yr,t,(t&1)});
    };
    auto calc=[&](int from,int l)->int {
        int v=from&1?s2:s1-1;
        if(l>v) return 10000000;
        int r=min(v/(v/l),maxx-a[from+1>>1].first);
        push(a[from+1>>1].first+l,a[from+1>>1].first+r,a[from+1>>1].second+1,a[from+1>>1].second+(v/l),from);
        return r+1;
    };
    for(i=1;i<=n;++i) {
        l[i*2-1]=calc(i*2-1,1);
        if(s1>1) l[i*2]=calc(i*2,1);
    }
    for(i=p=1;i<=maxx;++i) {
        while(p<=n&&a[p].first==i) {
            int x=a[p].second;
            for(j=belong[x]+1;j<=belong[maxy];++j)
                ++tag[j];
            for(j=x;belong[j]==belong[x];++j)
                ++pre[j];
            ++p;
        }
        now=ask[i],ask[i].clear();
        for(auto x:now) {
            if(x.t) ans+=(tag[belong[x.r]]+pre[x.r])-(tag[belong[x.l]]+pre[x.l]);
            else ans-=(tag[belong[x.r]]+pre[x.r])-(tag[belong[x.l]]+pre[x.l]);
            if(x.t==((x.from)&1)&&a[x.from+1>>1].first+l[x.from]<=maxx)
            l[x.from]=calc(x.from,l[x.from]);
        }
        for(auto x:ask[i]) {
            if(x.t) ans+=(tag[belong[x.r]]+pre[x.r])-(tag[belong[x.l]]+pre[x.l]);
            else ans-=(tag[belong[x.r]]+pre[x.r])-(tag[belong[x.l]]+pre[x.l]);
        }
        ask[i].clear();
        ask[i].shrink_to_fit();
    }
    printf("%lld\n",ans);
    return 0;
}