Submission #32574131

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
const ll mod=998244353;
#define rep(i,a) for (ll i=0;i<a;i++)


ll R=(mod+1)/2;
struct lazy_S {
    ll E;
    ll F;
    ll size;
};

using lazy_F = ll;

lazy_S lazy_op(lazy_S l, lazy_S r) {
    return lazy_S{
        (l.E+r.E+(l.F*r.size)%mod)%mod,(l.F+r.F)%mod,l.size+r.size
    };
}

lazy_S lazy_e() { return lazy_S{0, 0, 0}; }

lazy_S mapping(lazy_F l, lazy_S r) {
    l%=mod;
    if(l==0) return r;
    ll tmp=(r.size*(r.size+1))%mod;
    tmp*=(l*R)%mod;
    tmp%=mod;
    return lazy_S{
        (r.E+tmp)%mod,(r.F+(l*r.size)%mod)%mod,r.size
    };
}

//l(r(x))
lazy_F composition(lazy_F l, lazy_F r) {
    return (l+r)%mod;
}

lazy_F lazy_id(){return 0;}

#define lazy_calc lazy_S,lazy_op,lazy_e,lazy_F,mapping,composition,lazy_id


void solve();
// oddloop
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t=1;
    //cin>>t;
    rep(i,t) solve();
}

void solve(){
    int N,Q;
    cin>>N>>Q;
    lazy_segtree<lazy_calc> seg(N);
    vector<ll> A(N);
    rep(i,N) seg.set(i,{0,0,1});
    rep(i,N){
        ll a;
        cin>>a;
        A[i]=a;
        seg.apply(i,N,a);
    }
    rep(i,Q){
        int t;
        cin>>t;
        if(t==1){
            ll x,v;
            cin>>x>>v;
            x--;
            seg.apply(x,N,v-A[x]);
            A[x]=v;
        }else{
            ll x;
            cin>>x;
            cout<<(mod+seg.prod(0,x).E)%mod<<"\n";
        }
    }
}

Submission Info

Judge Result