結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー miya256
提出日時 2025-09-06 14:48:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,104 ms / 2,500 ms
コード長 3,540 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 135,344 KB
最終ジャッジ日時 2025-09-06 14:49:42
合計ジャッジ時間 44,770 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

class FenwickTree:
    def __init__(self, data):
        """data: list or len"""
        if isinstance(data, int):
            data = [0 for _ in range(data)]
        self._n = len(data)
        self._data = data
        self._tree = [0] * self._n
        self._all_sum = self._build(data)
    
    def _build(self, data):
        acc = [0] * (self._n+1)
        for i in range(1, self._n+1):
            acc[i] = acc[i-1] + data[i-1]
            self._tree[i-1] = acc[i] - acc[i-(-i&i)]
        return acc[-1]
    
    def __len__(self):
        return self._n
    
    def get(self, i):
        return self._data[i]
    
    def __getitem__(self, i):
        return self.get(i)
    
    def add(self, i ,x):
        """i番目にxを足す"""
        self._add(i, x)
    
    def set(self, i, x):
        """加えるではなく、更新"""
        self._add(i, x-self._data[i])
    
    def __setitem__(self, i, x):
        self.set(i, x)

    def sum(self, l, r):
        """[l,r)の和"""
        return self._sum(l, r)
    
    def all_sum(self):
        return self._all_sum
    
    def bisect_left(self, x):
        """累積和がx以上になるindex"""
        return self._bisect_left(x)
    
    def bisect_right(self, x):
        """累積和がxを超えるindex"""
        return self._bisect_right(x)
    
    def __str__(self):
        return f'FenwickTree {self._data}'
    
    def _add(self, i, x):
        self._data[i] += x
        self._all_sum += x
        i += 1
        while i <= self._n:
            self._tree[i-1] += x
            i += -i & i

    def _prefix_sum(self, i):
        sum = 0
        while i > 0:
            sum += self._tree[i-1]
            i -= -i & i
        return sum

    def _sum(self, l, r):
        return self._prefix_sum(r) - self._prefix_sum(l)
    
    def _bisect_left(self, x):
        i = 1 << self._n.bit_length()-1
        val = 0
        while not i & 1:
            if i-1 < self._n and val + self._tree[i-1] < x:
                val += self._tree[i-1]
                i += (-i & i) >> 1
            else:
                i -= (-i & i) >> 1
        return i-1 + (val + self._tree[i-1] < x)
    
    def _bisect_right(self, x):
        i = 1 << self._n.bit_length()-1
        val = 0
        while not i & 1:
            if i-1 < self._n and val + self._tree[i-1] <= x:
                val += self._tree[i-1]
                i += (-i & i) >> 1
            else:
                i -= (-i & i) >> 1
        return i-1 + (val + self._tree[i-1] <= x)
    
#aiを参照している岩井の数 * ai 加算

#l~rの和を加算
#u~vの和を減算
#->BIT
n,m = map(int,input().split())
ft = FenwickTree(m)
ft2 = FenwickTree(m+1) #何人から参照されてるか
home = []
l = []
r = []
a = []
for i in range(n):
    aa,ll,rr = map(int,input().split())
    home.append(i)
    l.append(ll-1)
    r.append(rr-1)
    a.append(aa)
    ft.add(i, aa)
    ft2.add(ll-1, 1)
    ft2.add(rr, -1)

ans = 0
for i in range(n):
    ans += a[i] * (r[i]-l[i]+1) - ft.sum(l[i], r[i]+1)

for _ in range(int(input())):
    x,y,u,v = map(lambda x:int(x)-1,input().split())
    ans -= a[x] * (r[x]-l[x]+1)
    ans += ft.sum(l[x], r[x]+1) #自分が参照してる分はここで

    ft2.add(l[x], -1)
    ft2.add(r[x]+1, 1)
    ans += a[x] * ft2.sum(0, home[x]+1)

    ft.add(home[x], -a[x])
    ft.add(y, a[x])
    home[x] = y

    ans += a[x] * (v-u+1)
    ans -= ft.sum(u, v+1)

    ans -= a[x] * ft2.sum(0, y+1)

    ft2.add(u, 1)
    ft2.add(v+1, -1)
    l[x] = u
    r[x] = v

    print(ans)
0