正题

---

题目大意

有若干个红点和蓝点，对于每一对红点和蓝点，若距离大于$D$则蓝点压制红点，否则红点压制蓝点。然后红点和蓝点之间也有不定的压制关系。

求有多少个三角要求$A$压制$B$，$B$压制$C$，$C$压制$A$且至少包含一个红点和蓝点。求三角数量的最小值和最大值。

---

解题思路

我们考虑最暴力的做法先，我们可以枚举两个相同颜色的点，枚举他们之间的关系，然后找三角。

我们定义$co{v}_x$表示在$x$的$D$范围以内与他异色的点的数量，$co{v}_{x,y}$表示同时在$x,y$两个点的$D$范围内的异色点的数量，对于包含两个红色点的方案数为
$$\sum _{x,y\in red}max\{co{v}_x-co{v}_{x,y},co{v}_y-co{v}_{x,y}\}$$
$$\sum _{x,y\in red}max\{co{v}_x,co{v}_y\}-co{v}_{x,y}$$
$$\sum _{x,y\in red}max\{co{v}_x,co{v}_y\}-\sum _{z\in blue}co{v}_{x,y}$$
那我们发现对于每个蓝点$z$被统计的次数就是$C_{co{v}_z}^2$
$$\Rightarrow \sum _{x,y\in red}max\{co{v}_x,co{v}_y\}-\sum _{z\in blue}{C}_{co{v}_z}^2$$
然后我们发现如果计算出$cov$数组即可在$O(n\log n)$的时间内统计答案（排个序瞎搞搞就好）

那如何统计$cov$数组，我们可以将每个点$(x,y)$转换为$(x-y,x+y)$然后将曼哈顿距离转换为切比雪夫距离。这样我们发现$cov$就是在$(x,y)$这个点为中心的$2D\ast 2D$的矩阵包含的点的个数，用扫描线统计即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=200100; struct node{ll x,y; }a[N],b[N]; ll n,m,D,y[N*3],mov,maxs,mins,covn[N],covm[N],cnt; struct Seq_node{struct Tree_node{ll l,r,w;}t[N*16];void Build(ll x,ll l,ll r){t[x].l=l;t[x].r=r;if(l==r) return;ll mid=(l+r)/2;Build(x*2,l,mid);Build(x*2+1,mid+1,r);}ll Ask(ll x,ll l,ll r){if(t[x].l==l&&t[x].r==r)return t[x].w;ll mid=(t[x].l+t[x].r)/2;if(r<=mid) return Ask(x*2,l,r);else if(l>mid) return Ask(x*2+1,l,r);else return Ask(x*2,l,mid)+Ask(x*2+1,mid+1,r);}void Change(ll x,ll pos,ll val){if(t[x].l==t[x].r){t[x].w+=val;return;}ll mid=(t[x].l+t[x].r)/2;if(pos<=mid) Change(x*2,pos,val);else Change(x*2+1,pos,val);t[x].w=t[x*2].w+t[x*2+1].w;} }T; bool cMp(node x,node y) {return x.x<y.x;} int main() {freopen("mhw.in","r",stdin);freopen("mhw.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&D);for(ll i=1;i<=n;i++){ll X,Y;scanf("%lld%lld",&X,&Y);a[i].x=X+Y;a[i].y=X-Y;y[++cnt]=a[i].y;y[++cnt]=a[i].y+D;y[++cnt]=a[i].y-D;}for(ll i=1;i<=m;i++){ll X,Y;scanf("%lld%lld",&X,&Y);b[i].x=X+Y;b[i].y=X-Y;y[++cnt]=b[i].y;y[++cnt]=b[i].y+D;y[++cnt]=b[i].y-D;} sort(b+1,b+1+m,cMp);sort(a+1,a+1+n,cMp);sort(y+1,y+1+cnt);cnt=unique(y+1,y+1+cnt)-(y+1);T.Build(1,1,cnt);ll l=0,r=0;for(ll i=1;i<=n;i++){while(l<m&&b[l+1].x<a[i].x-D){ll Y=lower_bound(y+1,y+1+cnt,b[++l].y)-y;T.Change(1,Y,-1);}while(r<m&&b[r+1].x<=a[i].x+D){ll Y=lower_bound(y+1,y+1+cnt,b[++r].y)-y;T.Change(1,Y,1);}ll L=lower_bound(y+1,y+1+cnt,a[i].y-D)-y,R=lower_bound(y+1,y+1+cnt,a[i].y+D)-y;covn[i]=T.Ask(1,L,R);}while(l<m){ll Y=lower_bound(y+1,y+1+cnt,b[++l].y)-y;T.Change(1,Y,-1);}while(r<m){ll Y=lower_bound(y+1,y+1+cnt,b[++r].y)-y;T.Change(1,Y,1);}l=0,r=0;for(ll i=1;i<=m;i++){while(l<n&&a[l+1].x<b[i].x-D){ll Y=lower_bound(y+1,y+1+cnt,a[++l].y)-y;T.Change(1,Y,-1);}while(r<n&&a[r+1].x<=b[i].x+D){ll Y=lower_bound(y+1,y+1+cnt,a[++r].y)-y;T.Change(1,Y,1);}ll L=lower_bound(y+1,y+1+cnt,b[i].y-D)-y,R=lower_bound(y+1,y+1+cnt,b[i].y+D)-y;covm[i]=T.Ask(1,L,R);}sort(covn+1,covn+1+n);sort(covm+1,covm+1+m);for(ll i=1;i<=n;i++)maxs+=covn[i]*(i-1),mins+=covn[i]*(n-i),mov+=covn[i]*(covn[i]-1)/2;for(ll i=1;i<=m;i++)maxs+=covm[i]*(i-1),mins+=covm[i]*(m-i),mov+=covm[i]*(covm[i]-1)/2;printf("%lld %lld",mins-mov,maxs-mov); }

总结

以上是生活随笔为你收集整理的jzoj6297-世界第一的猛汉王【切比雪夫距离,扫描线】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。