正題

題目鏈接:https://www.ybtoj.com.cn/contest/116/problem/2

---

題目大意

$n$個點(diǎn)，$x$坐標(biāo)遞增，第$i$個點(diǎn)向第$j$個點(diǎn)連邊。

開始一個人在點(diǎn)$s$，他會向他看到過的$y$坐標(biāo)最大的點(diǎn)的方向走（兩個點(diǎn)之間能夠看到當(dāng)且僅當(dāng)它們之間沒有邊或者點(diǎn)）。

求對于每個$s$走到$y$坐標(biāo)最大的點(diǎn)的經(jīng)過點(diǎn)數(shù)。

$y$值同樣的以編號大的算大

$1\le n\le 5\times 10^5,1\le x_i,y_i\le 10^6$

---

解題思路

先考慮每個點(diǎn)能看到的最高的點(diǎn)。

維護(hù)一個前綴的上凸殼，然后每次把該點(diǎn)連接的那個點(diǎn)就是這個點(diǎn)在凸殼方向能看到的最高的點(diǎn)。

左右各做一次就好了。

然后考慮怎么處理答案，先把所有點(diǎn)按照目標(biāo)點(diǎn)的高度排序，然后每個點(diǎn)找到它的方向上在它前面的第一個點(diǎn)作為它的真正目標(biāo)點(diǎn)。然后倒序轉(zhuǎn)移就好了。

找真正目標(biāo)點(diǎn)的過程可以反過來然后用鏈表實現(xiàn)

時間復(fù)雜度$O(n\log n)$（寫基排就$O(n)$了）

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e5+10; ll n,x[N],y[N],pos[N],s[N],l[N],r[N],p[N],f[N]; ll xj(ll a,ll b,ll c){ll x1=x[b]-x[a],y1=y[b]-y[a];ll x2=x[c]-x[a],y2=y[c]-y[a];return x1*y2-x2*y1; } bool cmp(ll a,ll b){return y[p[a]]*n+p[a]<y[p[b]]*n+p[b]; } signed main() { // freopen("mountain.in","r",stdin); // freopen("mountain.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]),pos[i]=i;ll top=0;s[++top]=1;for(ll i=2;i<=n;i++){while(top>1&&xj(s[top-1],s[top],i)>0)top--;p[i]=s[top];s[++top]=i;}top=1;s[top]=n;for(ll i=n-1;i>=1;i--){while(top>1&&xj(s[top-1],s[top],i)<0)top--;if(y[s[top]]>=y[p[i]])p[i]=s[top];s[++top]=i;}for(ll i=1;i<=n;i++)if(y[p[i]]*n+p[i]<y[i]*n+i)p[i]=0;y[0]=1e9;sort(pos+1,pos+1+n,cmp);for(ll i=1;i<=n;i++)l[i]=i-1,r[i]=i+1;for(ll i=1;i<n;i++){ll x=pos[i];if(p[x]>x)p[x]=r[x];else p[x]=l[x];l[r[x]]=l[x];r[l[x]]=r[x];}for(ll i=n-1;i>=1;i--){ll x=pos[i];f[x]=f[p[x]]+abs(p[x]-x);}for(ll i=1;i<=n;i++)printf("%lld\n",f[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的YbtOJ#482-爬上山顶【凸壳,链表】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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