正題

---

題目大意

有若干個(gè)紅點(diǎn)和藍(lán)點(diǎn)，對(duì)于每一對(duì)紅點(diǎn)和藍(lán)點(diǎn)，若距離大于$D$則藍(lán)點(diǎn)壓制紅點(diǎn)，否則紅點(diǎn)壓制藍(lán)點(diǎn)。然后紅點(diǎn)和藍(lán)點(diǎn)之間也有不定的壓制關(guān)系。

求有多少個(gè)三角要求$A$壓制$B$，$B$壓制$C$，$C$壓制$A$且至少包含一個(gè)紅點(diǎn)和藍(lán)點(diǎn)。求三角數(shù)量的最小值和最大值。

---

解題思路

我們考慮最暴力的做法先，我們可以枚舉兩個(gè)相同顏色的點(diǎn)，枚舉他們之間的關(guān)系，然后找三角。

我們定義$co{v}_x$表示在$x$的$D$范圍以內(nèi)與他異色的點(diǎn)的數(shù)量，$co{v}_{x,y}$表示同時(shí)在$x,y$兩個(gè)點(diǎn)的$D$范圍內(nèi)的異色點(diǎn)的數(shù)量，對(duì)于包含兩個(gè)紅色點(diǎn)的方案數(shù)為
$$\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}$$
那我們發(fā)現(xiàn)對(duì)于每個(gè)藍(lán)點(diǎn)$z$被統(tǒng)計(jì)的次數(shù)就是$C_{co{v}_z}^2$
$$?\sum _{x,y\in red}max\{co{v}_x,co{v}_y\}?\sum _{z\in blue}{C}_{co{v}_z}^2$$
然后我們發(fā)現(xiàn)如果計(jì)算出$cov$數(shù)組即可在$O(n\log n)$的時(shí)間內(nèi)統(tǒng)計(jì)答案（排個(gè)序瞎搞搞就好）

那如何統(tǒng)計(jì)$cov$數(shù)組，我們可以將每個(gè)點(diǎn)$(x,y)$轉(zhuǎn)換為$(x?y,x+y)$然后將曼哈頓距離轉(zhuǎn)換為切比雪夫距離。這樣我們發(fā)現(xiàn)$cov$就是在$(x,y)$這個(gè)點(diǎn)為中心的$2D?2D$的矩陣包含的點(diǎn)的個(gè)數(shù)，用掃描線統(tǒng)計(jì)即可。

---

$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); }

總結(jié)

以上是生活随笔為你收集整理的jzoj6297-世界第一的猛汉王【切比雪夫距离,扫描线】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。