正題

題目鏈接:http://www.ybtoj.com.cn/contest/119/problem/3

---

題目大意

給出$n$個點$(x_i,y_i)$，$m$次給出$(k_i,a_i)$表示標記所有滿足
$$y_j>\frac{k_i}{x_j^{a_i}}$$的未標記點

求每個點的標記時間

$1\le n,m\le 10^5,1<a_i<10$

---

解題思路

全是乘法所以可以先左右取$ln$就是
$$ln(y_j)>ln(k_i)?ln(x_j)\times a_i$$
把$x,y,k$取$ln$然后就是一個順眼的式子
$$x_j\times a_i+y_i>k_i$$
雖然原題說$(x_i,y_i)$是點，但是我們可以換個思路，把$(x_i,y_i)$看成邊（$f(z)=x_{i}z+y_i$），$(a_i,k_i)$看成是點，然后問在每條邊下面的編號最小的點是哪個。

這個就很好解決了，考慮整體二分。每次要考慮對于一條邊是否有在$[L,mid]$編號的點在它下面。可以對于所有的$[L,mid]$的點拿出來構成一個下凸殼，然后根據每條邊的斜率二分出一個最下面的點，然后只拿這個點判斷就好了。

這樣就是$O(n{\log }^{2}n)$的了，如果肯寫歸并排序和凸殼用單調隊列維護是可以做到$O(n\log n)$的

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+10; int n,m,f[N],s[N],p[N],p1[N],p2[N],top,pos[N]; double x[N],y[N],k[N],z[N]; double xj(double x1,double y1,double x2,double y2) {return x1*y2-x2*y1;} double xl(int a,int b,int c){double y1=k[b]-k[a],x1=z[b]-a[z];double y2=k[c]-k[a],x2=z[c]-z[a];return xj(x1,y1,x2,y2); } bool cmp(int x,int y) {return z[x]<z[y];} void solve(int Ln,int Rn,int Lm,int Rm){if(Ln>Rn)return;if(Lm==Rm){for(int i=Ln;i<=Rn;i++)f[p[i]]=Lm;return;}int mid=(Lm+Rm)>>1;top=0;sort(pos+Lm,pos+1+mid,cmp);for(int i=Lm;i<=mid;i++){while(top>1&&xl(s[top-1],s[top],pos[i])<=0)top--;s[++top]=pos[i];}sort(pos+Lm,pos+1+mid);int cnt1=0,cnt2=0;for(int i=Ln;i<=Rn;i++){int l=1,r=top-1;while(l<=r){int m=(l+r)>>1;if(xj(z[s[m+1]]-z[s[m]],k[s[m+1]]-k[s[m]],1,x[p[i]])>0)l=m+1;else r=m-1;}if(x[p[i]]*z[s[l]]+y[p[i]]>k[s[l]])p1[++cnt1]=p[i];else p2[++cnt2]=p[i];}for(int i=1;i<=cnt1;i++)p[i+Ln-1]=p1[i];for(int i=1;i<=cnt2;i++)p[Ln+cnt1+i-1]=p2[i];solve(Ln,Ln+cnt1-1,Lm,mid);solve(Ln+cnt1,Rn,mid+1,Rm);return; } int main() {freopen("analysis.in","r",stdin); // freopen("analysis.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lf%lf",&x[i],&y[i]);x[i]=log(x[i]);y[i]=log(y[i]);p[i]=i;}for(int i=1;i<=m;i++){scanf("%lf%lf",&k[i],&z[i]);k[i]=log(k[i]);pos[i]=i;}solve(1,n,1,m);for(int i=1;i<=n;i++)if(f[i]==m)puts("-1");else printf("%d\n",f[i]);return 0; }

總結

以上是生活随笔為你收集整理的YbtOJ#853-平面标记【整体二分,凸壳】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。