提出 #75559409

---

ソースコード 拡げる

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

struct SegTree{
    int size;
    vector<int>arr;
    vector<int>pre;
    vector<int>suf;
    vector<int>seg;
    vector<int>maxs;
    void init(int n){
        size = 1;
        while(size<n)size*=2;
        arr.assign(2*size,0LL);
        pre.assign(2*size,0LL);
        suf.assign(2*size,0LL);
        seg.assign(2*size,0LL);
        maxs.assign(2*size,0LL);
    }
    void set(int i, int v, int x, int lx, int rx){
        if(rx-lx==1){
            arr[x] = v;
            pre[x] = max(0LL,v);
            suf[x] = max(0LL,v);
            seg[x] = max(0LL,v);
            maxs[x] = v;
            return;
        }
        int m = (lx+rx)/2;
        if(i<m){
            set(i,v,2*x+1,lx,m);
        }
        else{
            set(i,v,2*x+2,m,rx);
        }
        arr[x] = arr[2*x+1]+arr[2*x+2];
        pre[x] = max(pre[2*x+1],arr[2*x+1]+pre[2*x+2]);
        suf[x] = max(suf[2*x+2],suf[2*x+1]+arr[2*x+2]);
        seg[x] = max(seg[2*x+1],max(seg[2*x+2],suf[2*x+1]+pre[2*x+2]));
        maxs[x] = max(maxs[2*x+1],maxs[2*x+2]);
    }
    void set(int i,int v){
        set(i,v,0,0,size);
    }
    vector<int> query(int l,int r, int x, int lx, int rx){
        vector<int>res(4);//sum,prefix,suffix,segment
        if(lx>=r||l>=rx)return {0,0,0,0};
        if(lx>=l&&rx<=r){
            res[0] = arr[x];
            res[1] = pre[x];
            res[2] = suf[x];
            res[3] = seg[x];
            return res;
        }
        int m = (lx+rx)/2;
        vector<int>res1 = query(l,r,2*x+1,lx,m);
        vector<int>res2 = query(l,r,2*x+2,m,rx);
        res[0] = res1[0]+res2[0];
        res[1] = max(res1[1],res1[0]+res2[1]);
        res[2] = max(res2[2],res1[2]+res2[0]);
        res[3] = max(res1[3],max(res2[3],res1[2]+res2[1]));
        return res;
    }
    int query(int l, int r){
        vector<int>res = query(l,r,0,0,size);
        return res[3];
    }
    int query2(int l,int r, int x, int lx, int rx){
        if(lx>=r||l>=rx)return -1*(int)1e9;
        if(lx>=l&&rx<=r)return maxs[x];
        int m = (lx+rx)/2;
        int s1 = query2(l,r,2*x+1,lx,m);
        int s2 = query2(l,r,2*x+2,m,rx);
        return max(s1,s2);
    }
    int query2(int l, int r){
        return query2(l,r,0,0,size);
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,q;
    cin >> n >> q;
    vector<int>a(n+1);
    int sum = 0;
    for(int i = 1; i<=n; i++){
        cin >> a[i];
        sum += a[i];
    }
    SegTree seg; seg.init(n+5);
    auto modify = [&](int i) -> void {
        if(a[i] == 0){
            seg.set(i,-1);
        }
        else{
            seg.set(i,a[i]);
        }
    };
    for(int i = 1; i<=n; i++){
        modify(i);
    }
    while(q--){
        int i,v;
        cin >> i >> v;
        sum -= a[i];
        a[i] = v;
        sum += a[i];
        modify(i);
        cout << sum - seg.query(1,n+1) << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果