模拟赛T1求调
  • 板块学术版
  • 楼主BPG_ning
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/10/15 18:36
  • 上次更新2023/11/2 13:36:12
查看原帖
模拟赛T1求调
551803
BPG_ning楼主2023/10/15 18:36
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
const LL inf=1e18+10;
int n,q,m;
LL a[N],b[N],c[N],sb[N],p[N];
LL sum,w[N];
struct Segment_Tree{
    LL Min[N<<2],lazy[N<<2];
    void build(int x,int L,int R){
        if(L==R){
            Min[x]=w[L];
            return ;
        }
        int mid=(L+R)>>1;
        build(x<<1,L,mid);
        build(x<<1|1,mid+1,R);
        pushup(x);
    }
    void pushup(int x){
        Min[x]=min(Min[x<<1],Min[x<<1|1]);
    }
    void pushdown(int x){
        if(lazy[x]==0) return ;
        lazy[x<<1]+=lazy[x];
        lazy[x<<1|1]+=lazy[x];
        Min[x<<1]+=lazy[x];
        Min[x<<1|1]+=lazy[x];
        lazy[x]=0;
    }
    void upd(int x,int L,int R,int l,int r,LL w){
        if(l<=L&&R<=r){
            Min[x]+=w;
            lazy[x]+=w;
            pushdown(x);
            return ;            
        }
        pushdown(x);
        int mid=(L+R)>>1;
        if(mid>=l) upd(x<<1,L,mid,l,r,w);
        if(mid+1<=r) upd(x<<1|1,mid+1,R,l,r,w);
        pushup(x);
    }
    LL query_Min(int x,int L,int R,int l,int r){
        pushdown(x);
        if(l<=L&&R<=r){
            return Min[x];
        }
        int mid=(L+R)>>1;
        LL ans=inf;
        if(mid>=l) ans=min(ans,query_Min(x<<1,L,mid,l,r));
        if(mid+1<=r) ans=min(ans,query_Min(x<<1|1,mid+1,R,l,r));
        return ans;
    }
}T;
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen("reserve.in","r",stdin);
    // freopen("reserve.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=n;i>=1;i--) sb[i]=sb[i+1]+b[i];
    for(int i=1;i<=n;i++) w[i]=sb[i+1]+a[i];
    cin>>q;
    T.build(1,1,n);
    while(q--){
        cin>>m;
        LL ans=sb[1];
        for(int i=1;i<=m;i++) cin>>p[i],ans-=b[p[i]];
        for(int i=1;i<=m;i++){
            if(p[i]!=1) T.upd(1,1,n,1,p[i]-1,-b[p[i]]);
            if(p[i]!=n) T.upd(1,1,n,p[i],n,c[p[i]]);
        }
        ans=min(ans,T.query_Min(1,1,n,1,n));
//        for(int i=1;i<=15;i++) cout<<i<<' '<<T.Min[i]<<' '<<T.lazy[i]<<'\n';
        cout<<ans<<'\n';
        for(int i=1;i<=m;i++){
            if(p[i]!=1) T.upd(1,1,n,1,p[i]-1,b[p[i]]);
            if(p[i]!=n) T.upd(1,1,n,p[i],n,-c[p[i]]);
        }
//        for(int i=1;i<=n;i++) if(T.query_Min(1,1,n,i,i)!=w[i]) cout<<"fuck!";
//        cout<<'\n';
    }
    return 0;
}

九十五分,WA最后一个点

2023/10/15 18:36
加载中...