网站建设方案书文库,wordpress在后台文章自定义表单,广州网站建设公,昆明自动seo正题
题目链接:https://www.luogu.com.cn/problem/P7408 题目大意
一个有n1n1n1层的地牢#xff0c;从iii到i1i1i1层要AiA_iAi点能量#xff0c;第iii层可以花费BiB_iBi获得111点能量。 mmm次询问从SiS_iSi层出发到第TiT_iTi层在能量上限为UiU_iUi的情况下至少需…正题
题目链接:https://www.luogu.com.cn/problem/P7408 题目大意
一个有n1n1n1层的地牢从iii到i1i1i1层要AiA_iAi点能量第iii层可以花费BiB_iBi获得111点能量。
mmm次询问从SiS_iSi层出发到第TiT_iTi层在能量上限为UiU_iUi的情况下至少需要花费多少。
1≤n,m≤2×1051\leq n,m\leq 2\times 10^51≤n,m≤2×105 解题思路
模型可以转换成坐标轴上有nnn个点第iii个在AiA_iAi考虑使用一个点获得的能量走的路就是这个点伸出的线覆盖的范围然后使得范围乘上BiB_iBi的和最小。
考虑能量上限的限制其实就是每个点覆盖的范围不能超过自身的UiU_iUi格。
考虑一个点覆盖范围根据UiU_iUi变化的变化
没有其他影响自己正常延伸此时覆盖范围为一个和UiU_iUi有关的一次函数延伸到下一个比自己大的位置不能继续延伸此时为一个常数上一个比自己小的数延伸过来此时为一个单调下降的一次函数完全被上一个比自己小的覆盖此时为000
也就是意味着每个点只需要考虑前后两个比自己小的数分成若干种情况即可。
考虑倒序枚举点然后用树状数组记录一次项系数的和与二次项系数的和。
对于结尾的限制我们找到能到达终点的最后的点直接走向它然后减去那个点的贡献即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includestack
#define ll long long
#define lowbit(x) (x-x)
using namespace std;
const ll N2e510,inf1e18;
struct node{ll l,r,u;
}q[N];
ll n,m,a[N],b[N],s[N],ans[N];
ll cnt,u[N],nxt[N],pre[N];
ll f[N][20],g[N][20],lg[N];
vectorll d[N],v[N];
stackll st;
ll rmqf(ll l,ll r){ll zlg[r-l1];lf[l][z];rf[r-(1z)1][z];return (b[l]b[r])?l:r;
}
ll rmqg(ll l,ll r){ll zlg[r-l1];lg[l][z];rg[r-(1z)1][z];return (a[l]a[r])?l:r;
}
struct TreeBinary{ll t[N];void Updata(ll x,ll val){while(xcnt){t[x]val;xlowbit(x);}return;}ll Ask(ll x){ll ans0;while(x){anst[x];x-lowbit(x);}return ans;}void Change(ll l,ll r,ll val){if(lr)return;llower_bound(u1,u1cnt,l)-u;rupper_bound(u1,u1cnt,r)-u;Updata(l,val);Updata(r,-val);return;}
}K,B;
signed main()
{scanf(%lld%lld,n,m);for(ll i1;in;i)scanf(%lld,a[i]),s[i1]s[i]a[i];for(ll i1;in;i)scanf(%lld,b[i]);for(ll i2;in1;i)lg[i]lg[i1]1;for(ll i1;in1;i)f[i][0]g[i][0]i;for(ll j1;(1j)n1;j)for(ll i1;i(1j)-1n1;i){ll xf[i][j-1],yf[i(1j-1)][j-1];f[i][j](b[x]b[y])?x:y;xg[i][j-1];yg[i(1j-1)][j-1];g[i][j](a[x]a[y])?x:y;}for(ll in;i1;i--){while(!st.empty()b[i]b[st.top()]){pre[st.top()]i;st.pop();}if(st.empty())nxt[i]n1;else nxt[i]st.top();st.push(i);}for(ll i1;im;i){scanf(%lld%lld%lld,q[i].l,q[i].r,q[i].u);u[i]q[i].u;ll laslower_bound(s1,s1n,s[q[i].r]-u[i])-s;lasmin(las,q[i].r-1);lasmax(min(las,q[i].r-1),q[i].l);lasrmqf(las,q[i].r-1);v[q[i].l].push_back(i);v[las].push_back(-i);ans[i](s[q[i].r]-s[las])*b[las];}sort(u1,u1m);cntunique(u1,u1m)-u-1;for(ll in;i1;i--){K.Change(0,s[nxt[i]]-s[i],b[i]);B.Change(s[nxt[i]]-s[i]1,inf,b[i]*(s[nxt[i]]-s[i]));d[pre[i]].push_back(i);for(ll j0;jd[i].size();j){ll xd[i][j];K.Change(s[x]-s[i],s[nxt[x]]-s[i],-b[x]);B.Change(s[x]-s[i],s[nxt[x]]-s[i],b[x]*(s[x]-s[i]));B.Change(s[nxt[x]]-s[i]1,inf,-b[x]*(s[nxt[x]]-s[x]));}for(ll j0;jv[i].size();j){ll xv[i][j],op1;if(x0)x-x,op-op;ll wlower_bound(u1,u1cnt,q[x].u)-u;ans[x]op*(q[x].u*K.Ask(w)B.Ask(w));}}for(ll i1;im;i){if(a[rmqg(q[i].l,q[i].r-1)]q[i].u)puts(-1);else printf(%lld\n,ans[i]);}return 0;
}
