毒瘤，毒瘤，毒瘤……

\(30000\)這個數據范圍，看上去就是要搞事的啊。。。

題目鏈接: https://www.lydsy.com/JudgeOnline/problem.php?id=2402

題解:

首先化式子: 假設二分的答案為\(mid\)則\(\frac{y_i+q_j}{x_i+p_j}\ge mid, y_i+q_j\ge mid(x_i+p_j), y_i-mid\times x_i+q_j-mid\times p_j\ge 0\)

那么我們實際上就是要找一個\(i\)使得\(-x_i\times mid+y_i\)最大，同理找一個\(j\)使得\(-p_j\times mid+q_j\)最大，這兩個任務完全一樣，現在就討論前者

為了方便(強迫癥)讓我們把它變成\(-a_ix+b_i\)的形式

仿照斜率優化的思路，如果\(a_i<a_j\)，那么\(i\)不劣于\(j\)當且僅當\(-a_ix+b_i\ge -a_jx+b_j, x\ge \frac{b_j-b_i}{a_j-a_i}\).

那么假設有并排著的三個點\(i,j,k,a_i<a_j<a_k\), 則\(i\)不劣于\(j\)當且僅當\(x\ge \frac{b_j-b_i}{a_j-a_i}\), \(k\)不劣于\(j\)當且僅當\(x\le \frac{b_k-b_j}{a_k-a_j}\), 如果\(\frac{b_j-b_i}{a_j-a_i}\le \frac{b_k-b_j}{a_k-a_j}\), 那么對于任何\(x\)上面兩個條件至少有一個成立，那么\(j\)就是無用的。也就是說有用的點一定滿足斜率遞減，在上凸殼的左半邊上。

這題沒有修改操作，那么我們可以用線段樹求出每個子區間內的凸殼，然后對于每個詢問，先分數規劃二分答案，然后求樹鏈剖分劃分成的每一段區間的最大值，這個可以通過在線段樹每個子區間的凸殼上二分得到。

時間復雜度\(O(n\log^4n)\)

(這可能是我最近寫的幾道題唯一一道跑進BZOJ前一半的？23333)

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<vector> using namespace std;const int N = 3e4; const double EPS = 1e-8; const double INF = 1e6; int dcmp(double x) {return x<-EPS ? -1 : (x>EPS ? 1 : 0);} struct Point {double x,y;Point() {}Point(double _x,double _y) {x = _x,y = _y;}bool operator <(const Point &arg) const {return dcmp(x-arg.x)<0 || (dcmp(x-arg.x)==0 && dcmp(y-arg.y)<0);} }; struct Edge {int v,w,nxt; } e[(N<<1)+3]; int fe[N+3]; int fa[N+3]; int dfn[N+3]; int idfn[N+3]; int sz[N+3]; int tpn[N+3]; int dep[N+3]; int hvs[N+3]; double a1[N+3],b1[N+3],a2[N+3],b2[N+3]; int n,q,en,cnt;struct SegmentTree {vector<Point> sgt[(N<<2)+3];void CHpush(int id,Point x){int j = sgt[id].size()-1;while(j>0 && dcmp((sgt[id][j].y-sgt[id][j-1].y)*(x.x-sgt[id][j].x)-(sgt[id][j].x-sgt[id][j-1].x)*(x.y-sgt[id][j].y))<=0){sgt[id].pop_back();j--;}sgt[id].push_back(x);}void build(int rtn,int le,int ri,double a[],double b[]){if(le==ri){sgt[rtn].push_back(Point(a[idfn[le]],b[idfn[le]]));return;}int mid = (le+ri)>>1;build(rtn<<1,le,mid,a,b);build(rtn<<1|1,mid+1,ri,a,b);int i = 0,j = 0;while(i<sgt[rtn<<1].size() && j<sgt[rtn<<1|1].size()){if(sgt[rtn<<1][i]<sgt[rtn<<1|1][j]) {CHpush(rtn,sgt[rtn<<1][i]); i++;}else {CHpush(rtn,sgt[rtn<<1|1][j]); j++;}}while(i<sgt[rtn<<1].size()) {CHpush(rtn,sgt[rtn<<1][i]); i++;}while(j<sgt[rtn<<1|1].size()) {CHpush(rtn,sgt[rtn<<1|1][j]); j++;}}double calc(int rtn,double x){int left = 0,right = sgt[rtn].size()-1;while(left<right){int mid = (left+right+1)>>1;if(mid==0) {break;}if(dcmp(x*(sgt[rtn][mid].x-sgt[rtn][mid-1].x)-(sgt[rtn][mid].y-sgt[rtn][mid-1].y))<=0) {left = mid;}else {right = mid-1;}}double ret = -sgt[rtn][left].x*x+sgt[rtn][left].y;return ret;}double query(int rtn,int le,int ri,int lb,int rb,double x){if(le>=lb && ri<=rb) {return calc(rtn,x);}int mid = (le+ri)>>1; double ret = -INF;if(lb<=mid) {ret = max(ret,query(rtn<<1,le,mid,lb,rb,x));}if(rb>mid) {ret = max(ret,query(rtn<<1|1,mid+1,ri,lb,rb,x));}return ret;} } sgt1,sgt2;void addedge(int u,int v) {en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en; }void dfs1(int u) {sz[u] = 1; hvs[u] = 0;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(v==fa[u]) continue;fa[v] = u;dep[v] = dep[u]+1;dfs1(v);sz[u] += sz[v];if(sz[v]>sz[hvs[u]]) {hvs[u] = v;}} }void dfs2(int u) {cnt++; dfn[u] = cnt; idfn[cnt] = u;if(hvs[u]) {tpn[hvs[u]] = tpn[u]; dfs2(hvs[u]);}for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(v==hvs[u] || v==fa[u]) continue;tpn[v] = v;dfs2(v);} }bool query(int u,int v,double x) {double ret1 = -INF,ret2 = -INF;while(tpn[u]!=tpn[v]){if(dep[fa[tpn[u]]]>dep[fa[tpn[v]]]){double tmp = sgt1.query(1,1,n,dfn[tpn[u]],dfn[u],x);ret1 = max(ret1,tmp);tmp = sgt2.query(1,1,n,dfn[tpn[u]],dfn[u],x);ret2 = max(ret2,tmp);u = fa[tpn[u]];}else{double tmp = sgt1.query(1,1,n,dfn[tpn[v]],dfn[v],x);ret1 = max(ret1,tmp);tmp = sgt2.query(1,1,n,dfn[tpn[v]],dfn[v],x);ret2 = max(ret2,tmp);v = fa[tpn[v]];}}if(dep[u]>dep[v]) swap(u,v);double tmp = sgt1.query(1,1,n,dfn[u],dfn[v],x);ret1 = max(ret1,tmp);tmp = sgt2.query(1,1,n,dfn[u],dfn[v],x);ret2 = max(ret2,tmp);if(dcmp(ret1+ret2)>0) return true;return false; }int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%lf",&a1[i]);for(int i=1; i<=n; i++) scanf("%lf",&b1[i]);for(int i=1; i<=n; i++) scanf("%lf",&a2[i]);for(int i=1; i<=n; i++) scanf("%lf",&b2[i]);for(int i=1; i<n; i++){int x,y; scanf("%d%d",&x,&y);addedge(x,y); addedge(y,x);}dep[1] = 1; dfs1(1);tpn[1] = 1; dfs2(1);sgt1.build(1,1,n,a1,b1);sgt2.build(1,1,n,a2,b2);scanf("%d",&q);for(int i=1; i<=q; i++){int x,y; scanf("%d%d",&x,&y);double left = 0.0,right = 1e5;while(right-left>5e-5){double mid = (left+right)*0.5;bool ans = query(x,y,mid);if(ans) {left = mid;}else {right = mid;}}printf("%lf\n",left);}return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 2402 陶陶的难题II (树链剖分、线段树、凸包、分数规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

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