fork download
copy 
  1. class FenwickTree:
  2.     def __init__(self, size):
  3.         self.size = size
  4.         self.tree = [0] * (size + 1)
  5.  
  6.     def update(self, idx, delta):
  7.         while idx <= self.size:
  8.             self.tree[idx] += delta
  9.             idx += idx & -idx
  10.  
  11.     def query(self, idx):
  12.         result = 0
  13.         while idx > 0:
  14.             result += self.tree[idx]
  15.             idx -= idx & -idx
  16.         return result
  17.  
  18.     def range_update(self, left, right, delta):
  19.         self.update(left, delta)
  20.         self.update(right + 1, -delta)
  21.  
  22.     def range_query(self, left, right):
  23.         return self.query(right) - self.query(left - 1)
  24.  
  25. # Read input
  26. import sys
  27. input = sys.stdin.read
  28. data = input().split()
  29.  
  30. N = int(data[0])
  31. Q = int(data[1])
  32.  
  33. # Read permutation P
  34. P = list(map(int, data[2:2 + N]))
  35.  
  36. # Initialize Fenwick Trees for original indices and permutation indices
  37. original_tree = FenwickTree(N)
  38. permutation_tree = FenwickTree(N)
  39.  
  40. output = []
  41. idx = 2 + N
  42. for _ in range(Q):
  43.     T = int(data[idx])
  44.     if T == 0:
  45.         l = int(data[idx + 1])
  46.         r = int(data[idx + 2])
  47.         c = int(data[idx + 3])
  48.         original_tree.range_update(l, r, c)
  49.         idx += 4
  50.     elif T == 1:
  51.         l = int(data[idx + 1])
  52.         r = int(data[idx + 2])
  53.         c = int(data[idx + 3])
  54.         permutation_tree.range_update(l, r, c)
  55.         idx += 4
  56.     elif T == 2:
  57.         l = int(data[idx + 1])
  58.         r = int(data[idx + 2])
  59.         result = original_tree.range_query(l, r)
  60.         output.append(result)
  61.         idx += 3
  62.     elif T == 3:
  63.         l = int(data[idx + 1])
  64.         r = int(data[idx + 2])
  65.         result = permutation_tree.range_query(l, r)
  66.         output.append(result)
  67.         idx += 3
  68.  
  69. # Print all results for the queries
  70. print("\n".join(map(str, output)))
  71.  
Success #stdin #stdout 0.03s 9736KB
comments (?)
stdin
copy 
5 6
3 1 5 4 2
0 2 4 2
1 2 4 3
2 3 4
0 2 5 1
3 2 4
3 1 3
stdout
copy 
0
3
3
https://ideone.com/ygxFlP
language:
Python 3 (python  3.9.5)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!