結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー 紫前燈太
提出日時 2025-09-06 14:44:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,737 ms / 2,500 ms
コード長 2,928 bytes
コンパイル時間 2,779 ms
コンパイル使用メモリ 207,708 KB
実行使用メモリ 25,504 KB
最終ジャッジ日時 2025-09-06 14:46:03
合計ジャッジ時間 41,153 ms
ジャッジサーバーID
（参考情報） 		judge / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <typename T>
struct ST_SUM{
    vector<T>num;
    int siz;

    ST_SUM(int n){
        int x = 1;
        while(n > x) x <<= 1;
        
        siz = x;
        num = vector<T> ((x<<1),0LL); 
    }

    void Update(int x,T i){ 
        x = x + siz - 1; 
        num[x] = i;

        while(x != 0){
            x = (x-1)/2; 
            num[x] = num[x*2 + 1]+num[x*2 + 2]; 
        }
    }

    T Sub_Serch(int n,int m,int k,int l,int r){
        if(r <= n || m <= l) return 0;
        if(n <= l && r <= m) return num[k];
        k *= 2; 
        T lx = Sub_Serch(n, m, k+1, l, (r+l)/2);
        T rx = Sub_Serch(n, m, k+2, (l+r)/2, r);

        return lx + rx; 
    }

    T Serch(int n,int m){
        return Sub_Serch(n, m+1, 0, 0, siz); 
    }
};

template <typename T>
struct ST_CNT{
    vector<T>num;
    int siz;

    ST_CNT(int n){
        int x = 1;
        while(n > x) x <<= 1;
        
        siz = x;
        num = vector<T> ((x<<1),0LL); 
    }

    void sub_update(int n,int m,int k,int l,int r,T x){
        if(r <= n || m <= l) return;
        if(n <= l && r <= m){
            num[k] += x;
            return;
        }

        k *= 2;
        sub_update(n,m,k+1,l,(l+r)/2,x);
        sub_update(n,m,k+2,(l+r)/2,r,x);

        return;
    }

    void update(int n,int m,T x){
        sub_update(n,m+1,0,0,siz,x);
        return;
    }

    T serch(int n){
        n += siz-1;
        
        T sum = num[n];
        while(n != 0){
            n = (n-1)/2;
            sum += num[n];
        }

        return sum;
    }
};

int main(){
    int n,m;
    cin >> n >> m;

    ST_SUM<ll>sum (m);
    ST_CNT<ll>cnt (m);

    vector<vector<int>>rng (n,vector<int>(2));
    vector<ll>rate (n),pos (n); 
    for(int i=0;i<n;i++){
        ll s,l,r;
        cin >> s >> l >> r;
        l--,r--;

        rng[i][0] = l,rng[i][1] = r;
        rate[i] = s;
        pos[i] = i;

        sum.Update(i,s);
        cnt.update(l,r,1);
    }

    ll ans = 0;
    for(int i=0;i<n;i++){
        ll c = sum.Serch(rng[i][0],rng[i][1]);
        ll d = rng[i][1] - rng[i][0] + 1;

        ans += d * rate[i] - c;
    }

    int q;
    cin >> q;

    for(int i=0;i<q;i++){
        int x,y,l,r;
        cin >> x >> y >> l >> r;
        x--,y--,l--,r--;

        ll bc = sum.Serch(rng[x][0],rng[x][1]);
        ll bd = rng[x][1] - rng[x][0] + 1;
        ans -= bd * rate[x] - bc;

        cnt.update(rng[x][0],rng[x][1],-1);
        ll c = cnt.serch(pos[x]);
        ans += c * rate[x];

        sum.Update(pos[x],0);
        pos[x] = y;
        sum.Update(pos[x],rate[x]);

        ll ac = cnt.serch(pos[x]);
        ans -= ac * rate[x];
        
        rng[x][0] = l,rng[x][1] = r;
        ll aac =  sum.Serch(l,r);
        ll aad =  r - l + 1;
        
        ans += rate[x] * aad - aac;
        cnt.update(l,r,1);

        cout << ans << endl;
    }
}
0