csp36-5 梦魔(30分)

csp36-5 梦魔

题干

https://sim.csp.thusaac.com/contest/36/problem/4

30分作答

#include<bits/stdc++.h>
using namespace std;

int n,q;
const int N=2e6+5;
int a[N],b[N];

int a_new[N],b_new[N];
bool check(long long bb,int i){//n个int相加会溢出，所以用long long
    int l=i,r=i+1;
    while(l>=0&&r<n){
        if(a_new[l]<=a_new[r]){
            if(bb<a_new[l]) return false;
            else{
                bb+=b_new[l];
                l--;
            }
        }else{
            if(bb<a_new[r]) return false;
            else{
                bb+=b_new[r];
                r++;
            }
        }
    }
    while(l>=0){
        if(bb<a_new[l]) return false;
        else{
            bb+=b_new[l];
            l--;
        }
    }
    while(r<n){
        if(bb<a_new[r]) return false;
        else{
            bb+=b_new[r];
            r++;
        }
    }

    return true;
}

void work(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];

    cin>>q;
    while(q--){
        int k;
        cin>>k;

        for(int i=0;i<n;i++){
            a_new[i]=a[i];
            b_new[i]=b[i];
        } 

        while(k--){//变动
            int j,aa,bb;
            cin>>j>>aa>>bb;
            a_new[j-1]=aa;
            b_new[j-1]=bb;
        }

        //设计让a的最大值作为二分的右边界
        int amax=-1;
        for(int i=0;i<n;i++) amax=max(amax,a_new[i]);

        int ans=0;
        for(int i=0;i<n-1;i++){
            int l=0,r=amax;
            while(l<r){
                int mid=l+r>>1;
                if(check(mid,i)) r=mid;//[l,mid]
                else l=mid+1;
            }
            // cout<<"p:"<<l<<endl;
            ans^=l;
        }

        cout<<ans<<endl;
    }

}

int main(){
    work();
    return 0;
}