Wuyanru's blog
0%

[UNR#4] 己酸集合

发表于 分类于 ，

本来想做半平面莫队题的，结果跳着跳着做到这题了，而且我还不会做，有点菜了（

给我干哪来了，这还是莫队吗。

题目链接。

题意

平面上有 个点，第 个点坐标是 。

给定 组询问，第 组询问有多少个点和 的距离不超过 。

，。

题解

首先来化式子。

可以发现 。

令 和 ，并且令 ，。

那么这个式子就相当于 ，现在询问变成了问一条直线 下方有多少个点。

考虑，如果所有 相同，那么这个题该怎么做。

这意味着所有的询问的直线斜率应当是相同的。

那么对于两个点 ，这两个点之间一定存在一种『先后顺序』，即两个点中一定有一个点更容易在直线下方。

具体来说，如果有 ，那么 就更容易在直线下方，因为可以发现此时若 在直线下放， 也一定在直线下方。

那么这种情况下我们直接按照 从小到大的顺序将所有点排序，然后询问的时候二分一下就行。

那么如果 不相同的情况呢，还是考虑两个点 。

可以发现当 时 更容易，当 时 更容易。

我们不妨将所有询问按照 从小到大进行排序，并且维护所有点构成的这个序列。

当斜率变大时，可能有相邻的点在这个序列中被交换，但是交换的总次数不会超过 。

所以这样就可以得到一个 的做法。

考虑把所有点每 个点分一块，一共 块，每一块分开做这个东西。

那么时间复杂度应该是 。

取 ，时间复杂度是 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct ques
{
    ll k,b;
    int id;
}b[1000005];
struct node
{
    ll x,y;
}a[12005];
ll mem[12005];
int qans[1000005];
int n,q,sq=1;
inline ll ceil(ll x,ll y)// y>0
{
    if(x>=0) return (x+y-1)/y;
    return -(-x/y);
}
inline ll get(int p)
{
    int q=p+1;
    if(a[p].x>=a[q].x) return inf;
    return ceil(a[q].y-a[p].y,a[q].x-a[p].x);
}
set<pli>S;
inline void ins(int p)
{
    mem[p]=get(p);
    if(mem[p]!=inf) S.insert(pli(mem[p],p));
}
inline void erase(int p)
{
    if(mem[p]!=inf) S.erase(pli(mem[p],p));
}
inline void run(int l,int r)
{
    sort(a+l,a+r+1,[](node a,node b)
    {
        if(a.x!=b.x) return a.x<b.x;
        return a.y<b.y;
    });
    S.clear();
    for(int i=l;i<r;i++) ins(i);

    for(int i=1;i<=q;i++)
    {
        while(S.size()&&S.begin()->first<=b[i].k)
        {
            int p=S.begin()->second;S.erase(S.begin());
            swap(a[p],a[p+1]);
            if(p>l) erase(p-1),ins(p-1);
            if(p+1<r) erase(p+1),ins(p+1);
        }
        int L=l-1,R=r;
        while(L<R)
        {
            int mid=(L+R+1)>>1;
            if(a[mid].y<=b[i].k*a[mid].x+b[i].b) L=mid;
            else R=mid-1;
        }
        qans[b[i].id]+=L-l+1;
    }
}
int main()
{
    n=read(),q=read();
    while((sq+1)*(sq+1)<=q) sq++;
    for(int i=1;i<=n;i++)
    {
        ll X=lread(),Y=lread();
        a[i].x=2*Y,a[i].y=X*X+Y*Y;
    }
    for(int i=1;i<=q;i++)
    {
        ll z=read(),r=read();
        b[i].k=z,b[i].b=r*r-z*z,b[i].id=i;
    }
    sort(b+1,b+q+1,[](ques a,ques b){ return a.k<b.k;});
    for(int l=1,r;l<=n;l=r)
    {
        r=min(n+1,l+sq);
        run(l,r-1);
    }
    for(int i=1;i<=q;i++) printf("%d\n",qans[i]);
    return 0;
}