网站怎么做团购,公司官网如何更新网站,池州专业网站建设怎么样,网站域名代备案正题
题目链接:https://www.ybtoj.com.cn/problem/463 题目大意
给出长度为nnn的序列A,BA,BA,B。要求划分成若干段满足
对于任何ijijij#xff0c;若iii和jjj不是同一段的#xff0c;要求满足BiAjB_iA_jBiAj每一段AiA_iAi的最大值的和不能超…正题
题目链接:https://www.ybtoj.com.cn/problem/463 题目大意
给出长度为nnn的序列A,BA,BA,B。要求划分成若干段满足
对于任何ijijij若iii和jjj不是同一段的要求满足BiAjB_iA_jBiAj每一段AiA_iAi的最大值的和不能超过mmm
要求最小化每一段BiB_iBi和的最大值。
n∈[1,105],Ai,Bi∈[1,109],m∈[1,1012]n\in[1,10^5],A_i,B_i\in[1,10^9],m\in[1,10^{12}]n∈[1,105],Ai,Bi∈[1,109],m∈[1,1012] 解题思路
最大值最小化很显然直接二分然后变为求每一段AiA_iAi最大值的和的最小值。
第一个条件相当于限制了什么位置能够作为划分段的末尾求一个前缀min{bi}min\{b_i\}min{bi}和一个后缀max{ai}max\{a_i\}max{ai}能够快速求出这些位置。
然后考虑dpdpdp转移方程就是 fimin{fjmax{ak}(k∈(j,i])}f_imin\{f_jmax\{a_k\}(\ k\in(j,i]\ )\}fimin{fjmax{ak}( k∈(j,i] )}
二分的条件限制了jjj的范围加个指针就好了
这个东西好像很难搞但是注意到vjmax{ak}v_jmax\{a_k\}vjmax{ak}这一部分是递减的并且每次会让所有viv_ivi的一起和一个一起取maxmaxmax。
因为是递减的所以每次加入一个新的就相当于修改一段后缀的viv_ivi然后求一个区间的最大fivif_iv_ifivi了。
可以线段树维护每个节点维护该区间最大的fivif_iv_ifivi和最大的fif_ifi。区间推平viv_ivi的时候就可以拿最大的fif_ifi来更新fivif_iv_ifivi
时间复杂度O(nlognlog∑bi)O(n\log n\log\sum b_i)O(nlognlog∑bi) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,inf1e97;
ll n,m,a[N],b[N],pre[N],suf[N],last[N];
ll lg[N],st[N][17],v[N2],w[N2],lazy[N2];
void Downdata(ll x){if(!lazy[x])return;lazy[x*2]lazy[x*21]lazy[x];w[x*2]v[x*2]lazy[x];w[x*21]v[x*21]lazy[x];lazy[x]0;return;
}
void Changew(ll x,ll L,ll R,ll l,ll r,ll val){if(lr)return;if(LlRr){w[x]v[x]val;lazy[x]val;return;}ll mid(LR)1;Downdata(x);if(rmid)Changew(x*2,L,mid,l,r,val);else if(lmid)Changew(x*21,mid1,R,l,r,val);else Changew(x*2,L,mid,l,mid,val),Changew(x*21,mid1,R,mid1,r,val);w[x]min(w[x*2],w[x*21]);
}
void Changev(ll x,ll l,ll r,ll pos,ll val){if(lr){v[x]val;w[x]v[x]lazy[x];return;}ll mid(lr)1;Downdata(x);if(posmid)Changev(x*2,l,mid,pos,val);else Changev(x*21,mid1,r,pos,val);w[x]min(w[x*2],w[x*21]);v[x]min(v[x*2],v[x*21]);return;
}
ll Ask(ll x,ll L,ll R,ll l,ll r){if(LlRr)return w[x];ll mid(LR)1;Downdata(x);if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return min(Ask(x*2,L,mid,l,mid),Ask(x*21,mid1,R,mid1,r));
}
ll RMQ(ll l,ll r){ll zlg[r-l1];return max(st[l][z],st[r-(1z)1][z]);
}
bool check(ll x){memset(v,0x3f,sizeof(v));memset(w,0x3f,sizeof(w));memset(lazy,0,sizeof(lazy));ll sum0,l0,tmpv[0];Changev(1,0,n,0,0);for(ll i1;in;i){sumb[i];while(sumx)l,sum-b[l];Changew(1,0,n,last[i],i-1,a[i]);if(pre[i]suf[i1])continue;tmpAsk(1,0,n,l,i);Changev(1,0,n,i,tmp);}return (tmpm);
}
signed main()
{freopen(sequence.in,r,stdin);freopen(sequence.out,w,stdout);scanf(%lld%lld,n,m);ll l1,r0;pre[0]inf;for(ll i1;in;i)scanf(%lld%lld,a[i],b[i]),rb[i],lmax(l,b[i]),st[i][0]a[i];for(ll i2;in;i)lg[i]lg[i1]1;for(ll j1;(1j)n;j)for(ll i1;i(1j)-1n;i)st[i][j]max(st[i][j-1],st[i(1j-1)][j-1]);for(ll i1;in;i){ll l1,ri-1;while(lr){ll mid(lr)1;if(RMQ(mid,i)a[i])lmid1;else rmid-1;}last[i]r;}for(ll i1;in;i)pre[i]min(pre[i-1],b[i]);for(ll in;i1;i--)suf[i]max(suf[i1],a[i]);while(lr){ll mid(lr)1;if(check(mid))rmid-1;else lmid1;}check(l1);printf(%lld\n,l);
}
