Wuyanru's blog
0%

[Ynoi Easy Round 2021] TEST_136

发表于 分类于 ，

我其实是来学半平面莫队的（。

这题肯定也能半平面莫队做但是感觉半平面莫队很难写，网上也没找到相关资料。

题目链接。

题意

给定 个点，第 个点坐标是 ，颜色是 。

次询问，每一次给定一个半平面 ，求有多少对 满足 都在这个半平面内且 。

，。

题解

考虑先得会这个题，仍然考虑旋转扫描线。

将所有点按照颜色进行排序，然后每 个分一块，分成 块。

考虑这么一个事情，如果一个颜色只在单独一块出现过了，那么这个颜色的贡献只和这一个块有关系，称这种颜色为『一类颜色』。

否则的话，这个颜色至少在两个块里面出现过，称这种颜色为『二类颜色』。

由于我们将所有点按照颜色排序，所以，一个块内至多有两种二类颜色。

那么现在考虑如何进行询问，对所有块同时跑旋转扫描线。

考虑此时我们的操作有两种：

  1. 交换某个块中相邻两个点的顺序；
  2. 进行一次询问，每一个块内一个前缀的点会在询问的范围内。

考虑对一类颜色和二类颜色分别计算答案。

对于一类颜色，只需要对块内单独计算，考虑处理出每一个前缀的答案。

考虑每一次交换相邻两个点，只会有一个前缀的答案改变，所以我们只需要知道，每一个点，他前面有多少个同颜色点就好了。

这是容易单次 维护的。

对于二类颜色，我们直接维护，块内每一个前缀的二类颜色出现次数。

由于每一个块里面至多有两种二类颜色， 所以我们直接 for 一圈就能算出来了。

由于每一次询问的时候，需要二分来确定前缀，所以复杂度为 。

取 ，得复杂度为 。

神秘的卡常小技巧：跑旋转扫描线的时候不要用 set，直接初始化的时候把任意两点直接斜率 sort 一下，直接就能得到交换点的顺序。

sort 这部分改成基数排序可以做到 。

代码

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#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;
}
const ld PI=acos(-1);
struct node
{
    ll x,y;
    int c,id;
}a[50005];
struct ques
{
    ll A,B,C;
    int id;
    inline bool check(ll x,ll y)
    {
        return A*x+B*y+C<0;
    }
}b[500005];
struct frac
{
    ll x,y;int p,q;
    frac(ll x=0,ll y=0,int p=0,int q=0):x(x),y(y),p(p),q(q){}
    bool operator <= (frac b) const
    {
        return x*b.y<=y*b.x;
    }
};
vc<frac>wtf[50005];
ll qans[500005];
int c1[50005],c2[50005];
int pre1[50005],pre2[50005];
int suf1[50005],suf2[50005];
int vp[50005],vs[50005];
int idp[50005],ids[50005];
int cnt[50005],rid[50005];
bool vis[50005];
int wh[50005];
int L[50005];
int R[50005];
int n,m,sq=1;
vc<int>nod;
inline ld slope(ll x,ll y)
{
    if(x>0||(x==0&&y<0)) x=-x,y=-y;
    swap(x,y),y=-y;
    return atan2(y,x);
}
inline ll p2(ll v){ return v*v;}
inline void swap(int p)
{
    // printf("swap %d\n",p);
    int id=wh[p],q=p+1;
    // swap a[p] and a[q]
    swap(a[p],a[q]);rid[a[p].id]=p,rid[a[q].id]=q;
    if(a[p].c!=a[q].c) swap(idp[p],idp[q]),swap(ids[p],ids[q]);
    if(p>L[id]) pre1[p]=pre1[p-1],pre2[p]=pre2[p-1],vp[p]=vp[p-1];else pre1[p]=pre2[p]=vp[p]=0;
    if(vis[a[p].c]) a[p].c==c1[id]?pre1[p]++:pre2[p]++;else vp[p]+=p2(idp[p])-p2(idp[p]-1);
    if(q<R[id]) suf1[q]=suf1[q+1],suf2[q]=suf2[q+1],vs[q]=vs[q+1];else suf1[q]=suf2[q]=vs[q]=0;
    if(vis[a[q].c]) a[q].c==c1[id]?suf1[q]++:suf2[q]++;else vs[q]+=p2(ids[q])-p2(ids[q]-1);
}
int main()
{
    n=read(),m=read();
    for(;(sq+1)*(sq+1)<=m;sq++);
    for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].c=read();
    sort(a+1,a+n+1,[](node a,node b){ return a.c<b.c;});
    for(int i=1;i<=m;i++) b[i].A=read(),b[i].B=read(),b[i].C=read(),b[i].id=i;
    sort(b+1,b+m+1,[](ques a,ques b){ return slope(a.B,-a.A)<slope(b.B,-b.A);});

    for(int i=1,l=1,r;l<=n;l=r,i++)
    {
        r=min(l+sq,n+1);
        L[i]=l,R[i]=r-1;
        for(int j=l;j<r;j++) wh[j]=i;
        vis[a[L[i]].c]=vis[a[R[i]].c]=1;
        c1[i]=a[L[i]].c,c2[i]=a[R[i]].c;
        sort(a+L[i],a+R[i]+1,[](node a,node b)
        {
            if(a.x!=b.x) return a.x<b.x;
            return a.y<b.y;
        });

        for(int j=L[i];j<=R[i];j++)
        {
            a[j].id=j,rid[j]=j;
            // printf("(%lld,%lld) %c",a[j].x,a[j].y," \n"[j==n]);
            if(j>L[i]) pre1[j]=pre1[j-1],pre2[j]=pre2[j-1],vp[j]=vp[j-1];
            if(vis[a[j].c]) a[j].c==c1[i]?pre1[j]++:pre2[j]++;
            else idp[j]=++cnt[a[j].c],vp[j]+=p2(idp[j])-p2(idp[j]-1);
        }
        for(int j=R[i];j>=L[i];j--)
        {
            if(j<R[i]) suf1[j]=suf1[j+1],suf2[j]=suf2[j+1],vs[j]=vs[j+1];
            if(vis[a[j].c]) a[j].c==c1[i]?suf1[j]++:suf2[j]++;
            else ids[j]=cnt[a[j].c]-idp[j]+1,vs[j]+=p2(ids[j])-p2(ids[j]-1);
        }

        for(int p=L[i];p<=R[i];p++) for(int q=p+1;q<=R[i];q++) if(a[p].x<=a[q].x)
            wtf[i].push_back(frac(a[q].y-a[p].y,a[q].x-a[p].x,p,q));
        sort(wtf[i].rbegin(),wtf[i].rend(),[](frac a,frac b)
        {
            ll v1=a.x*b.y,v2=a.y*b.x;
            if(v1!=v2) return v1<v2;
            if(a.p!=b.p) return a.p<b.p;
            return a.q<b.q;
        });
    }

    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++) if(vis[i]) nod.push_back(i);
    for(int i=1;i<=m;i++)
    {
        // printf("i=%d : %lldx+%lldy+%lld<0\n",i,b[i].A,b[i].B,b[i].C);

        ll ans=0;frac V;bool f;
        if(b[i].B>0||(b[i].B==0&&b[i].A>0)) V=frac(-b[i].A,b[i].B,-1,-1),f=0;
        else V=frac(b[i].A,-b[i].B,-1,-1),f=1;

        // printf("V= %lld/%lld\n",V.x,V.y);

        for(int j=1;j<=wh[n];j++)
        {
            // j : L[j] ~ R[j]
            if(b[i].B)
            {
                while(wtf[j].size()&&wtf[j].back()<=V)
                {
                    int p=wtf[j].back().p;
                    wtf[j].pop_back();
                    swap(rid[p]);
                }
            }
            if(!f)
            {
                //pre
                int l=L[j]-1,r=R[j];
                while(l<r)
                {
                    int mid=(l+r+1)>>1;
                    if(b[i].check(a[mid].x,a[mid].y)) l=mid;
                    else r=mid-1;
                }
                if(l>=L[j])
                {
                    ans+=vp[l];
                    cnt[c1[j]]+=pre1[l];
                    cnt[c2[j]]+=pre2[l];
                }
            }
            else
            {
                //suf
                int l=L[j],r=R[j]+1;
                while(l<r)
                {
                    int mid=(l+r)>>1;
                    if(b[i].check(a[mid].x,a[mid].y)) r=mid;
                    else l=mid+1;
                }
                if(l<=R[j])
                {
                    ans+=vs[l];
                    cnt[c1[j]]+=suf1[l];
                    cnt[c2[j]]+=suf2[l];
                }
            }
        }
        for(int p:nod) ans+=p2(cnt[p]),cnt[p]=0;
        qans[b[i].id]=ans;
    }
    for(int i=1;i<=m;i++) printf("%lld\n",qans[i]);
    return 0;
}