90pts 求助 WA#3#4(悬赏一关注)
查看原帖
90pts 求助 WA#3#4(悬赏一关注)
398310
hundunqidian楼主2023/10/17 19:27
#include<bits/stdc++.h>
#define int long long
#define rs(rt) rt<<1|1
#define ls(rt) rt<<1

using namespace std;
inline void rd(int &r){
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0' || ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}
	r=x*f;
	return ;
}
inline void out(int x){
	if(x>9) out(x/10);
	putchar('0'+x%10);
	return ;
}
int const X=5e5+100;
int n,a[X],b[X],c[X];
int q,m,p[X]; 
int pre[X],suf0[X],suf[X],ans;
int t[X<<2] ;
void build(int rt,int l,int r){
	if(l==r){
		t[rt]=suf0[l+1]+a[l];
		//前面全部赋为0,后面暴力修改0 
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(rt),l,mid);
	build(rs(rt),mid+1,r);
	t[rt]=min(t[ls(rt)],t[rs(rt)]);
	return ;
}
int query(int rt,int l,int r,int ul,int ur){
	if(l>r || ul>ur) return 1e16;
	if(ul<=l&&r<=ur){
		return t[rt];
	}
	int mid=(l+r)>>1,res=1e16;
	if(ul<=mid){
		res=min(res,query(ls(rt),l,mid,ul,ur));
	}
	if(mid+1<=ur){
		res=min(res,query(rs(rt),mid+1,r,ul,ur)) ;
	}
	return res;
}
/*
pre:区间赋值后,暴力把前面的0修改回来 +
suf0:暴力修改后面的1为0 +
suf:统计后面不需要暴力修改为0的位置 -
*/
signed main(){
	rd(n);
	for(int i=1;i<=n;i++){
		rd(a[i]);
	}
	for(int i=1;i<=n;i++){
		rd(b[i]);
	}
	for(int i=1;i<=n;i++){
		rd(c[i]);
	}
	for(int i=n;i>=1;i--){
		suf0[i]=suf0[i+1]+b[i];
	}
	build(1,1,n); 
	rd(q);
	p[0]=0;
	while(q--){
		rd(m);
		for(int i=1;i<=m;i++){
			rd(p[i]);
			pre[p[i]]=c[p[i]];
			suf[p[i]]=b[p[i]];
		}
		for(int i=1;i<=m;i++){
			pre[p[i]]+=pre[p[i-1]];
		}
		for(int i=m;i>=1;i--){
			suf[p[i]]+=suf[p[i+1]];
		}
		ans=suf0[1]-suf[1]; //全部单点修改 
		for(int i=1;i<=m+1;i++){
			int lx=1,rx=n;
			if(i!=1) lx=p[i-1]+1;
			if(i!=m+1) rx=p[i]-1;
			//在[p[i-1]+1,p[i]-1]区间内寻找综合费用最小的 
			ans=min(ans,query(1,1,n,lx,rx)+pre[p[i-1]]-suf[p[i]]);
			if(i<=m) {
				//在p[i]处修改 
				ans=min(ans,a[p[i]]+pre[p[i]]+suf0[p[i]]-suf[p[i]]);
			}
		}
		out(ans); putchar('\n');
		for(int i=0;i<=m;i++){
			suf[p[i]]=pre[p[i]]=0; 
			p[i]=0;
		}
	}
	return 0;
}
2023/10/17 19:27
加载中...