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.         for i in range(l, r + 1):
  55.             permutation_tree.update(P[i - 1], c)
  56.         idx += 4
  57.     elif T == 2:
  58.         l = int(data[idx + 1])
  59.         r = int(data[idx + 2])
  60.         result = original_tree.range_query(l, r)
  61.         output.append(result)
  62.         idx += 3
  63.     elif T == 3:
  64.         l = int(data[idx + 1])
  65.         r = int(data[idx + 2])
  66.         result = 0
  67.         for i in range(l, r + 1):
  68.             result += permutation_tree.query(P[i - 1]) - permutation_tree.query(P[i - 1] - 1)
  69.         output.append(result)
  70.         idx += 3
  71.  
  72. # Print all results for the queries
  73. print("\n".join(map(str, output)))
  74.  
Success #stdin #stdout 0.03s 9816KB
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
9
6
https://ideone.com/cFu4Uu
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!