本蒟蒻代码思路同题解第二页第一个线段树,倒着考虑。
感谢观看蒟蒻代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define M 100010
using namespace std;
inline int read(){
int x=0;int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar(); }
return x*f;
}
int n,ans[M];
struct Node{
int id,val;
}h[M];int s[M],a[M];
inline Node Min(Node a,Node b){
if(a.val==b.val){
return a.id<b.id?a:b;
}else{
return a.val<b.val?a:b;
}
}
inline int lowbit(int x){return x&-x;}
inline void Mi_update(int x,int w){
h[x]=((Node){x,w});
for(;x<=n;x+=lowbit(x))
for(int i=1;i<lowbit(x);i<<=1)
h[x]=Min(h[x],h[x-i]);
}
inline Node Mi_qurry(int x,int y){
Node res=((Node){0,inf});
while(y>=x){
Node may=((Node){y,a[y]});
res=Min(res,may);
for(y=y-1;y-lowbit(y)>=x;y-=lowbit(y))
res=Min(res,h[y]);
}
return res;
}
int pre[M],nxt[M];
inline void Delete(int pos){
pre[nxt[pos]]=pre[pos];
nxt[pre[pos]]=nxt[pos];
}
int main(){
n=read();
for(int i=1;i<=n;++i)s[i]=read();
for(int i=1;i<=n;++i){
a[i]=read();
Mi_update(i,a[i]);
pre[i]=i-1;
nxt[i]=i+1;
ans[n]+=a[i];
}
int l=1,r=n;
ans[n]+=s[r]*2;
for(int i=n-1;i>=1;--i){
Node tmp=Mi_qurry(l,r-1);
int an=ans[i+1]-tmp.val;
int an_=ans[i+1]-a[r]-s[r]*2+s[pre[r]]*2;
if(an<an_){
int nr=r;
r=pre[r];Delete(nr);ans[i]=an_;
}else{//感觉这个删除有问题
Delete(tmp.id);a[tmp.id]=inf;
Mi_update(tmp.id,inf);ans[i]=an;
}
}
for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
return 0;
}
若daloa也用的树状数组,可以发给我借鉴一下,
但还是希望帮帮我看看qwq