題目描述：

小 D 喜歡出毒瘤題毒人。當然，他的毒瘤更多體現在若干個難題組合在同一場比賽時。

小 D 腦中有 $n$ 個毒瘤題 idea，第 $i$ 個的毒值為$d_i$。當第 $i$ 個題和第 $j$ 個題同時出現在一場比賽中，會產生$f(i,j) = d_i + d_j$ 的毒性。

小 D 決定用這些題在 YLOJ 上辦 $m$ 場在線比賽。

? 由于這個 OJ 還在~~咕咕~~開發(fā)，YLOJ Extremelyhard Round #i 選取的題目編號集合只能為 $[l_i,r_i]$ 的一個非空子區(qū)間 $[a_i,b_i]$。

? 因為這個 round 是 extremelyhard 的，所以需要滿足$\sum\limits_{a_i \le j,k \le b_i} f(j,k) \ge x_i$。

? 不過，為了防止題目過分毒瘤而被噴，小 D 希望最小化$max_{a_i \le j \le b_i} \{d_i\}$，而你需要告訴他這個最小值。

算法標簽：線段樹

思路：

對于一個區(qū)間的答案，可以分為三類，一類是以區(qū)間的左端點作為選擇的區(qū)間作為左端點，一類是以區(qū)間的右端點作為選擇區(qū)間的右端點，一類是左右端點在區(qū)間中間，受某個最大值的限制而不能擴大區(qū)間。

因為權值都是正數，所以對于一個選擇的區(qū)間如果固定左端點，恰好滿足總和限制的最小的區(qū)間最優(yōu)，根據這個可以先二分計算出第一類和第二類的答案。

考慮第三類，我們對于每一個點求出它作為最大值可以延伸的最大區(qū)間。然后當這個區(qū)間被詢問區(qū)間包含的時候，可以對答案造成貢獻，但是這樣是三維的。我們會發(fā)現如果你選擇左端點在詢問左端點和這個詢問第二類求的答案區(qū)間的左端點左側，這個時候你的答案一旦超過詢問區(qū)間，這個答案一定沒有單獨取右區(qū)間優(yōu)，所以只需要滿足左端點在范圍內，區(qū)間權值大于詢問。是一個二維偏序，可以用線段樹維護得到答案。

以下代碼：

#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=3e5+5,inf=1e9; int n,m,a[N],res[N],tot,Lg[N],st[N][20]; LL sum[N];int mn[N<<2]; struct node{int l,r,ll,id;LL val; }t[N]; struct data{int l,r,mx;LL val; }g[N]; il LL read(){LL x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x; } bool cmp(node t1,node t2){return t1.val>t2.val; } bool cmp1(data t1,data t2){return t1.val>t2.val; } il int getmax(int l,int r){if(l>r)swap(l,r);int k=Lg[r-l+1];return max(st[l][k],st[r-(1<<k)+1][k]); } il int getl(int x,int v){int l=1,r=x,res=x;while(l<=r){int mid=(l+r)>>1;if(getmax(mid,x)<=v)res=mid,r=mid-1;else l=mid+1;}return res; } il int getr(int x,int v){int l=x,r=n,res=x;while(l<=r){int mid=(l+r)>>1;if(getmax(mid,x)<=v)res=mid,l=mid+1;else r=mid-1;}return res; } il LL cal(int l,int r){return (sum[r]-sum[l-1])*(r-l+1)*2; } il int gl(int ql,int qr,LL v){int l=ql,r=qr,res=ql;while(l<=r){int mid=(l+r)>>1;if(cal(ql,mid)>=v)res=mid,r=mid-1;else l=mid+1;}return res; } il int gr(int ql,int qr,LL v){int l=ql,r=qr,res=qr;while(l<=r){int mid=(l+r)>>1;if(cal(mid,qr)>=v)res=mid,l=mid+1;else r=mid-1;}return res; } il void insert(int x,int l,int r,int pos,int v){if(l==r){mn[x]=min(mn[x],v);return;}int mid=(l+r)>>1;if(pos<=mid)insert(x<<1,l,mid,pos,v);else insert(x<<1|1,mid+1,r,pos,v);mn[x]=min(mn[x<<1],mn[x<<1|1]); } il int query(int x,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return mn[x];int mid=(l+r)>>1;int res=inf;if(ql<=mid)res=query(x<<1,l,mid,ql,qr);if(mid<qr)res=min(res,query(x<<1|1,mid+1,r,ql,qr));return res; } int main() {n=read();m=read();for(int i=1;i<=n;i++)st[i][0]=a[i]=read(),sum[i]=sum[i-1]+a[i];for(int i=2;i<=n;i++)Lg[i]=Lg[i>>1]+1;for(int j=1;j<=Lg[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);for(int i=1;i<=n;i++){int l=getl(i,a[i]),r=getr(i,a[i]);LL v=(sum[r]-sum[l-1])*(r-l+1)*2;g[i]=(data){l,r,a[i],v};}for(int i=1;i<=m;i++){int l=read(),r=read();LL x=read();if((sum[r]-sum[l-1])*(r-l+1)*2<x)res[i]=-1;else{int ll=gl(l,r,x),rr=gr(l,r,x);t[++tot]=(node){l,r,rr,i,x};res[i]=min(getmax(l,ll),getmax(rr,r));}}sort(t+1,t+1+tot,cmp);sort(g+1,g+1+n,cmp1);int now=1;for(int i=1;i<=n*4;i++)mn[i]=inf;for(int i=1;i<=tot;i++){while(g[now].val>=t[i].val){insert(1,1,n,g[now].l,g[now].mx),now++;}res[t[i].id]=min(res[t[i].id],query(1,1,n,t[i].l,t[i].ll));}for(int i=1;i<=m;i++)printf("%d\n",res[i]);return 0; } View Code

?

轉載于:https://www.cnblogs.com/Jessie-/p/10577660.html

總結

以上是生活随笔為你收集整理的dtoj#4263. duliu的全部內容，希望文章能夠幫你解決所遇到的問題。

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