#include #include #include using namespace std; using ll = long long; struct lazytree{ int N, iden, lazyiden; vector tree, lazy; int pow2(int n){ int ans=1; while(ans& a, int n){ N=pow2(n); iden=0, lazyiden=0; tree.resize(2*N, iden), lazy.resize(2*N, lazyiden); for(int i=0; i=1; i--) tree[i]=tree[2*i]+tree[2*i+1]; } void eval(int k, int l, int r){ if(lazy[k]!=lazyiden){ tree[k]+=lazy[k]*(r-l+1); //lazy[k]の値に強制的に切り替えられるのがquery if(l!=r){ lazy[2*k]+=lazy[k]; lazy[2*k+1]+=lazy[k]; } lazy[k]=lazyiden; } } void update(int s, int t, ll x, int k=1, int l=1, int r=-1){ //s, tは1-indexed! if(r<0) r=N; eval(k, l, r); if(t> n >> m; vector a(n), l(n), r(n), b(m), po(m), house(n); for(int i=0; i> a[i] >> l[i] >> r[i], house[i]=i+1, po[i]=a[i]; int q; cin >> q; lazytree seg, sum; seg.build(b, m); sum.build(po, m); for(int i=0; i> x >> y >> u >> v; x--; ans-=a[x]*(r[x]-l[x]+1); //cout << "A " << a[x]*(r[x]-l[x]+1) << endl; ans+=a[x]*seg.query(house[x], house[x]); //cout << "B " << a[x]*seg.query(house[x], house[x]) << endl; ans+=sum.query(l[x], r[x]); if(l[x]<=house[x]&&house[x]<=r[x]) ans-=a[x]; //cout << "C" << endl; sum.update(house[x], house[x], -a[x]); //cout << "D" << endl; seg.update(l[x], r[x], -1); l[x]=u, r[x]=v, house[x]=y; seg.update(l[x], r[x], 1); //cout << "E" << endl; sum.update(house[x], house[x], a[x]); ans-=sum.query(l[x], r[x]); if(l[x]<=house[x]&&house[x]<=r[x]) ans+=a[x]; ans+=a[x]*(r[x]-l[x]+1); //cout << "C " << a[x]*(r[x]-l[x]+1) << endl; ans-=a[x]*seg.query(house[x], house[x]); //cout << "D " << a[x]*seg.query(house[x], house[x]) << endl; cout << ans << '\n'; } return 0; }