[GDKOI模拟2016.01.26][JZOJ4218]補給站

題目大意

平面上有兩個圓，坐标分别為 (xa,ya) 、 (xb,yb) ，還有 n 個點，坐标分别為(xi,yi)。

有 q 個詢問，每次給出兩個圓各自半徑r1和 r2 。要求輸出有多少個點被至少一個圓覆寫（圓周也算在内）。

本題所有數字都為整數。

1≤n≤200000,1≤q≤100000,−100000≤x,y≤100000,0≤r≤300000

題目分析

一個點 (x,y) 在半徑為 r 、圓心為(x0,y0)的圓内（或圓上）當且僅當：

(x0−x)2+(y0−y)2≤r2

在題目中圓心和點的位置都是在詢問前知道的，于是我們提前計算每個點與兩個圓心不等式左邊式子的值，也就是到圓心距離的平方，用這兩個值作為新的關鍵字。

那麼給出 r 之後，小于等于r2的關鍵字個數就是被這個圓覆寫的點的個數。

如果是一個圓，那我們直接快排二分就行了，但是這裡是兩個圓，答案為兩個圓各自覆寫的點的個數和減去同時覆寫的點的個數。

怎麼求同時滿足兩個小于等于的限制的點的個數呢？我們将兩個新的關鍵字（ xn 和 yn ）作為每個點的坐标，那麼這個限制就可以看成平面中一個小平面 [0...xn][0...yn] 内點的個數。

顯然我們可以對其中一維排序，另一位離散化之後在資料結構中插值。顯然這裡選用主席樹是最好的。

時間複雜度 O((n+q)logn2) ，空間複雜度 O(nlogn2) 。

當然，這是這題對詢問線上的做法，如果通過對詢問離線的方法，我們可以用更加簡單的樹狀數組等資料結構來做，空間複雜度可以降為 O(n) 。個人認為主席樹代碼複雜度并不大，換離線方法也不會好到哪裡去，于是在這裡不讨論離線做法。

代碼實作

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long LL;

int read()
{
    int x=,f=;
    char ch=getchar();
    while (!isdigit(ch))
    {
        if (ch=='-')
            f=-;
        ch=getchar();
    }
    while (isdigit(ch))
    {
        x=x*+ch-'0';
        ch=getchar();
    }
    return x*f;
}

const int N=;
const int S=;

struct P
{
    int xn,yn;
    LL x,y;
    P (LL x0=,LL y0=){x=x0,y=y0;}
}p[N+],A,B;

P operator-(P a,P b)
{
    return P(a.x-b.x,a.y-b.y);
}

struct D
{
    LL v;
    int id,rank;
}s[][N+];

bool operator<(D a,D b)
{
    return a.v<b.v;
}

int n,m,cnt1,cnt2;

struct Chairman_Tree
{
    int son[S+][],size[S+];
    int root[N+];
    int tot;

    void init()
    {
        memset(son,,sizeof son);
        memset(size,,sizeof size);
        memset(root,,sizeof root);
        tot=;
        root[]=newnode();
    }

    int newnode()
    {
        son[tot][]=son[tot][]=size[tot]=;
        return tot++;
    }

    void insert(int &rt,int rt0,int l,int r,int x)
    {
        rt=newnode();
        son[rt][]=son[rt0][];
        son[rt][]=son[rt0][];
        size[rt]=size[rt0]+;
        if (l==r)
            return;
        int mid=l+r>>;
        if (x<=mid)
            insert(son[rt][],son[rt0][],l,mid,x);
        else
            insert(son[rt][],son[rt0][],mid+,r,x);
    }

    int query(int rt,int st,int en,int l,int r)
    {
        if (!rt)
            return ;
        if (st==l&&en==r)
            return size[rt];
        int mid=l+r>>;
        if (en<=mid)
            return query(son[rt][],st,en,l,mid);
        else
            if (mid+<=st)
                return query(son[rt][],st,en,mid+,r);
            else
                return query(son[rt][],st,mid,l,mid)+query(son[rt][],mid+,en,mid+,r);
    }
}t;

int main()
{
    freopen("supply.in","r",stdin);
    freopen("supply.out","w",stdout);
    n=read(),m=read();
    A.x=read(),A.y=read(),B.x=read(),B.y=read();
    for (int i=;i<=n;i++)
        p[i].x=read(),p[i].y=read();
    for (int i=;i<=n;i++)
    {
        P pa=p[i]-A,pb=p[i]-B;
        s[][i].v=pa.x*pa.x+pa.y*pa.y,s[][i].v=pb.x*pb.x+pb.y*pb.y;
        s[][i].id=i,s[][i].id=i;
    }
    sort(s[]+,s[]++n);
    sort(s[]+,s[]++n);
    s[][].v=-;
    cnt1=;
    for (int i=;i<=n;i++)
    {
        p[s[][i].id].xn=(s[][i].v!=s[][i-].v)?++cnt1:cnt1;
        s[][i].rank=cnt1;
    }
    s[][].v=-;
    cnt2=;
    for (int i=;i<=n;i++)
    {
        p[s[][i].id].yn=(s[][i].v!=s[][i-].v)?++cnt2:cnt2;
        s[][i].rank=cnt2;
    }
    t.init();
    for (int i=;i<=n;i++)
        t.insert(t.root[i],t.root[i-],,cnt2,p[s[][i].id].yn);
    for (int i=,r1,r2;i<=m;i++)
    {
        r1=read(),r2=read();
        LL s1=(LL)r1*r1,s2=(LL)r2*r2;
        int l=,r=n,p1=;
        while (l<=r)
        {
            int mid=l+r>>;
            if (s[][mid].v<=s1)
            {
                p1=mid;
                l=mid+;
            }
            else
                r=mid-;
        }
        int p2=;
        l=,r=n;
        while (l<=r)
        {
            int mid=l+r>>;
            if (s[][mid].v<=s2)
            {
                p2=mid;
                l=mid+;
            }
            else
                r=mid-;
        }
        p2=s[][p2].rank;
        int ans1=p2?t.query(t.root[n],,p2,,cnt2):;
        int ans2=t.query(t.root[p1],,cnt2,,cnt2);
        int ans3=p2?t.query(t.root[p1],,p2,,cnt2):;
        ans1=ans1+ans2-ans3;
        printf("%d\n",ans1);
    }
    fclose(stdin);
    fclose(stdout);
    return ;
}