求助,#3 #4WA
查看原帖
求助,#3 #4WA
746943
xijiu楼主2023/10/15 20:05
rt
#include<iostream>
#include<cstdio>
#define int long long 
using namespace std;
const int maxn=5e5+10,maxn1=2e3+10;
struct node{
	int l,r,minn;
}tr[maxn*4];
void pushup(int root){
	tr[root].minn=min(tr[root<<1].minn,tr[root<<1|1].minn);
}
int a[maxn],b[maxn],c[maxn];
int f[maxn],ans[maxn];
int f1[maxn];
int d[maxn];
int la[maxn];
int minn=1e18+10;
int sum=0;
int flag=0;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void build(int root,int l,int r){	
		tr[root].l=l;
		tr[root].r=r;
	if(l==r){
		tr[root].minn=f[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	pushup(root);
}
int quest(int root,int l,int r){
	if(tr[root].l>=l&&tr[root].r<=r){ 
		return tr[root].minn;
	}

	int minn1=1e18+10;
	int mid=(tr[root].l+tr[root].r)>>1;
	if(mid>=l)minn1=min(minn1,quest(root<<1,l,r));
	if(mid<r)minn1=min(minn1,quest(root<<1|1,l,r));
	return minn1;
}


signed main(){
//	freopen("t15.in","r",stdin);
//	freopen("t1.out","w",stdout);
	int n;
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i++){
		b[i]=read();
		sum+=b[i];
	}
	for(int i=1;i<=n;i++){
		c[i]=read();
	}
	for(int i=n;i>=1;i--){
		f1[i]=f1[i+1]+b[i];
	}
	for(int i=1;i<=n;i++){
		f[i]=f1[i+1]+a[i];
		minn=min(minn,f1[i+1]+a[i]);
	}
	int q;
	build(1,1,n);
	q=read();

	while(q--){
		int m;
		m=read();
	d[m+1]=0;
		for(int i=1;i<=m;i++){
			d[i]=read();
		}
		
		int ans=1e18+10;
		int la1=0;
		for(int i=1;i<=m;i++)la1+=b[d[i]];
		int fr1=0;
		if(d[1]==1){
			ans=min(ans,sum-la1);
		}
		else ans=min(ans,quest(1,1,d[1]-1)-la1);
		for(int i=1;i<=m-1;i++){
			fr1+=c[d[i]];
			la1-=b[d[i]];
			ans=min(ans,quest(1,d[i],d[i+1]-1)+fr1-la1);
		}
		fr1+=c[d[m]];
		la1=0;
		if(m==0&&n==1){
			ans=min(a[1],b[1]);
			printf("%lld",ans);
			continue ;
		}
		 ans=min(ans,quest(1,d[m],n)+fr1);
		printf("%lld\n",ans);
	}
	return 0;
} 
2023/10/15 20:05
加载中...