（未完待续）

题目链接：GMOJ 6297/九校联考 2018 D2T3。

题目

题目描述

输入格式

输出格式

样例输入输出

数据范围

时空限制

题解

先放一下代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::swap;
using std::pair;
using std::make_pair;
using std::sort;
using std::lower_bound;
#include<vector>
using std::vector;
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=100000+5;
struct Node{
    ll x,y;
    int val;
    inline Node(void){
        return;
    }
    inline Node(ll a,ll b,int c){
        x=a,y=b,val=c;
        return;
    }
    inline bool operator<(const Node &a)const{
        return x<a.x;
    }
};
struct TreeArray{
    int n,unit[MAXN*3];
    #define lowbit(x) ( (x) & ( - (x) ) )
    inline void Init(int num){
        n=num;
        memset(unit,0,sizeof(unit));
        return;
    }
    inline void Update(int ID,int val){
        while(ID<=n){
            unit[ID]+=val;
            ID+=lowbit(ID);
        }
        return;
    }
    inline int Query(int ID){
        register int sum=0;
        while(ID){
            sum+=unit[ID];
            ID-=lowbit(ID);
        }
        return sum;
    }
};
int n,m,D;
int covered[MAXN];
ll Min,Max,Another;//Min,Max是加的总和，Another是减的总和
TreeArray T;
pair<ll,ll> W[MAXN],B[MAXN];
vector<Node> E;//扫描线事件
vector<ll> Listx,Listy;//x离散化列表，y离散化列表
inline int GetID_of_y(ll);
inline void Solve(int,int,pair<ll,ll>[],pair<ll,ll>[]);
int main(void){
    freopen("mhw.in","r",stdin);
    freopen("mhw.out","w",stdout);
    register int i;
    n=read(),m=read(),D=read();
    //scanf("%d%d%d",&n,&m,&D);
    for(i=1;i<=n;++i){
        static int x,y;
        x=read(),y=read();
        //scanf("%d%d",&x,&y);
        W[i]=make_pair(x+y,x-y);
    }
    for(i=1;i<=m;++i){
        static int x,y;
        x=read(),y=read();
        //scanf("%d%d",&x,&y);
        B[i]=make_pair(x+y,x-y);
    }
    sort(W+1,W+n+1);
    sort(B+1,B+m+1);//排序
    Solve(n,m,W,B);//第一次
    Solve(m,n,B,W);//交换参数，重做
    printf("%lld %lld\n",Min-Another,Max-Another);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
inline int GetID_of_y(ll n){//离散化后查询序号
    return lower_bound(Listy.begin(),Listy.end(),n)-Listy.begin()+1;
}
inline void Solve(int n,int m,pair<ll,ll>W[],pair<ll,ll>B[]){
    register int i,j,k;
    E.clear();
    Listx.clear();
    Listy.clear();
    for(i=1;i<=m;++i){
        E.push_back(Node(B[i].first-D,B[i].second,1));
        E.push_back(Node(B[i].first+D+1,B[i].second,-1));
        Listx.push_back(B[i].first-D);
        Listx.push_back(B[i].first+D+1);
        Listy.push_back(B[i].second);
    }
    for(i=1;i<=n;++i){
        Listx.push_back(W[i].first);
        Listy.push_back(W[i].second-D-1);
        Listy.push_back(W[i].second+D);
    }
    sort(E.begin(),E.end());
    sort(Listx.begin(),Listx.end());
    sort(Listy.begin(),Listy.end());
    Listx.erase(unique(Listx.begin(),Listx.end()),Listx.end());
    Listy.erase(unique(Listy.begin(),Listy.end()),Listy.end());
    T.Init(Listy.size());
    for(i=j=0,k=1;i<(int)Listx.size();++i){
        ll x=Listx[i];
        while(j<(int)E.size()&&E[j].x==x){//更新
            T.Update(GetID_of_y(E[j].y),E[j].val);
            ++j;
        }
        while(k<=n&&W[k].first==x){//统计答案
            covered[k]=T.Query(GetID_of_y(W[k].second+D))-T.Query(GetID_of_y(W[k].second-D-1));//询问离散化的纵坐标的区间和
            ++k;
        }
    }
    sort(covered+1,covered+n+1);
    for(i=1;i<=n;++i){
        Min+=(ll)(n-i)*covered[i];//n-i个比它大
        Max+=(ll)(n-i)*covered[n-i+1];//n-i个比它小
        Another+=(ll)covered[i]*(covered[i]-1)>>1;//加到减的总和里面
    }
    return;
}