結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー Rumain831
提出日時 2025-09-06 14:24:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,225 ms / 2,500 ms
コード長 2,817 bytes
コンパイル時間 1,099 ms
コンパイル使用メモリ 84,628 KB
実行使用メモリ 29,012 KB
最終ジャッジ日時 2025-09-06 14:25:07
合計ジャッジ時間 49,821 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;

struct lazytree{
  int N, iden, lazyiden;
  vector<ll> tree, lazy;
  int pow2(int n){
    int ans=1;
    while(ans<n) ans*=2;
    return ans;
  }
  
  void build(vector<ll>& 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<n; i++) tree[N+i]=a[i];
    for(int i=N-1; 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<l||r<s) return;
    if(s<=l&&r<=t){
      lazy[k]+=x;
      eval(k, l, r);
      return;
    }
    else{
      int mid=(l+r)/2;
      update(s, t, x, 2*k, l, mid);
      update(s, t, x, 2*k+1, mid+1, r);
      tree[k]=tree[2*k]+tree[2*k+1];
    }
    return;
  }

  ll query(int s, int t, int k=1, int l=1, int r=-1){ //s, tは1-indexed!
    if(r<0) r=N;
    eval(k, l, r);
    if(t<l||r<s) return iden;
    if(s<=l&&r<=t) return tree[k];
    int mid=(l+r)/2;
    ll A=query(s, t, 2*k, l, mid);
    ll B=query(s, t, 2*k+1, mid+1, r);
    return A+B;
  }
};


int main(void){
  int n, m; cin >> n >> m;
  vector<ll> a(n), l(n), r(n), b(m), po(m), house(n);
  for(int i=0; i<n; i++) cin >> 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<n; i++){
    seg.update(l[i], r[i], 1);
  }
  ll ans=0;
  for(int i=0; i<n; i++){
    ans+=a[i]*(r[i]-l[i]+1);
    ans-=a[i]*seg.query(house[i], house[i]);
  }
  //cout << ans << endl;
  while(q--){
    int x, y, u, v; cin >> 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;
}
0