526互联

IOI 2007 Pairs

发布时间 2023-11-21 12:10:45作者: yl_neo
IOI 2007 Pairs

可以考虑三个情况：

若B=1:

这其实好像没什么好说的？lower_bound就可以轻轻松松30分

code:
void solve1(){
    for(int i=0;i<N;i++){
        std::cin>>a[i];
    }
    sort(a,a+N);
    i64 ans=0;
    for(int i=0;i<N;i++){
        int lst=lower_bound(a,a+N,a[i]-D)-a;
        ans+=i-lst;
    }
    std::cout<<ans<<'\n';
}

若B=2:

这就需要一些观察了：

考虑分成四个式子可以发现到 $(x,y)$到$(a,b)$的距离为：

if $x-a \geq 0$  and  $y-b \geq 0$, $dis = x-a+y-b = (x+y)-(a+b)$

if $x-a < 0$  and  $y-b \geq 0$, $dis = a-x+y-b = (a-b)-(x-y)$

if $x-a \geq 0$  and  $y-b < 0$, $dis = x-a+b-y = (x-y)-(a-b)$

if $x-a < 0$  and  $y-b < 0$, $dis = a-x+b-y = (a+b)-(x+y)$

$(x+y,x-y)$ 和 $(a+b,a-b)$的切比雪夫距离 $max(|(x+y)-(a+b)|, |(x-y)-(a-b)|)$ = $(x,y)$ 和 $(a,b)$ 的曼哈顿距离

结论：转换成$(x+y,x-y)$然后求矩阵$[x+y-d,x-y+d]$ 至 $[x+y,x-y+d]$ 的和。

维护双指针然后利用一个树状结构来维护区间值就可以了.

code:
i64 tr[NN<<1];
void update(int x,i64 v){
    x+=NN;
    for(;x;x=x/=2){ tr[x]+=v;}
}
i64 get(int x,int y){
    x+=NN; y+=NN;
    i64 res=0;
    while(x<=y){
        if(x%2==1) res+=tr[x++];
        if(y%2==0) res+=tr[y--];
        x/=2; y/=2;
    }
    return res;
}
void solve2(){
    vector<int> pos[75000*2+500];
    i64 ans=0;
    for(int i=0;i<N;i++){
        std::cin>>x[i]>>y[i];
        pos[x[i]+y[i]].push_back(x[i]-y[i]+M);
    }
    for(int i=2;i<=2*M;i++){
        for(auto &u:pos[i]){
            ans+=get(max(0,u-D),min(2*M,u+D));
            update(u,1);
        }
        if(i-D<=0) continue;
        for(auto &u:pos[i-D]) update(u,-1);
    }
    std::cout<<ans<<'\n';
}

 


 
若B=3：
我本人是不太会的但是看了别人的讲解，大概是拆成八个式子然后利用数值很小的原因，开桶然后就利用类似B=2的方式去解。


以下代码只能过B=1/2:

有时间的话我会修改成B=1/2/3
/*
Problem: IOI 2007 Pairs
When:    2023-11-16 14:54:19
Author:  Ning07
*/
 
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
 
constexpr int NN=2e5;
int N,B,M,D,a[NN],x[NN],y[NN];
 
void solve1(){
    for(int i=0;i<N;i++){
        std::cin>>a[i];
    }
    sort(a,a+N);
    i64 ans=0;
    for(int i=0;i<N;i++){
        int lst=lower_bound(a,a+N,a[i]-D)-a;
        ans+=i-lst;
    }
    std::cout<<ans<<'\n';
}
i64 tr[NN<<1];
void update(int x,i64 v){
    x+=NN;
    for(;x;x=x/=2){ tr[x]+=v;}
}
i64 get(int x,int y){
    x+=NN; y+=NN;
    i64 res=0;
    while(x<=y){
        if(x%2==1) res+=tr[x++];
        if(y%2==0) res+=tr[y--];
        x/=2; y/=2;
    }
    return res;
}
void solve2(){
    vector<int> pos[75000*2+500];
    i64 ans=0;
    for(int i=0;i<N;i++){
        std::cin>>x[i]>>y[i];
        pos[x[i]+y[i]].push_back(x[i]-y[i]+M);
    }
    for(int i=2;i<=2*M;i++){
        for(auto &u:pos[i]){
            ans+=get(max(0,u-D),min(2*M,u+D));
            update(u,1);
        }
        if(i-D<=0) continue;
        for(auto &u:pos[i-D]) update(u,-1);
    }
    std::cout<<ans<<'\n';
}
void solve3(){
    std::cout<<"?\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
 
    std::cin>>B>>N>>D>>M;
    if(B==1) solve1();
    else if(B==2) solve2();
    else if(B==3) solve3();
}

$+M$是为了更好地询问, $y-d$不会成负数