Submission #70986192

---

Source Code Expand

import sys
input = sys.stdin.readline

MAXV = 500000

class Fw:
  def __init__(self, n):
    self.n = n
    self.b = [0]*(n+1)
  def add(self, i, x):
    while i <= self.n:
      self.b[i] += x
      i += i & -i
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.b[i]
      i -= i & -i
    return s

fwc = Fw(MAXV+2)
fws = Fw(MAXV+2)

def pc(v):
  if v < 0: return 0
  if v > MAXV: v = MAXV
  return fwc.sum(v+1)

def ps(v):
  if v < 0: return 0
  if v > MAXV: v = MAXV
  return fws.sum(v+1)

n, q = map(int, input().split())
a = list(map(int, input().split()))

for v in a:
  fwc.add(v+1, 1)
  fws.add(v+1, v)

ans = []

for _ in range(q):
  t, *z = map(int, input().split())
  if t == 1:
    x, y = z
    x -= 1
    o = a[x]
    if o != y:
      fwc.add(o+1, -1)
      fws.add(o+1, -o)
      fwc.add(y+1, 1)
      fws.add(y+1, y)
      a[x] = y
  else:
    l, r = z
    if l > r:
      ans.append(str(l*n))
      continue
    c1 = pc(l-1)
    c2 = pc(r)
    c3 = n - c2
    sb = ps(r) - ps(l-1)
    v = l*c1 + sb + r*c3
    ans.append(str(v))

print("\n".join(ans))

Submission Info

Judge Result