fork download 
  1. import sys
  2. import math
  3.  
  4. MAX_VAL = 500005
  5. temp_counts = [0] * MAX_VAL
  6.  
  7. def calculate_beauty_direct(a, l, r):
  8.     for i in range(len(temp_counts)):
  9.         temp_counts[i] = 0
  10.  
  11.     for i in range(l, r + 1):
  12.         temp_counts[a[i]] += 1
  13.  
  14.     beauty = 0
  15.     # In the original C++, the loop limit is N, assuming values are <= N.
  16.     # We will iterate only over values present to be safe and efficient.
  17.     # To be a 1:1 translation, we would need to know the max possible value in a.
  18.     # The below is a slightly more Pythonic way for the same result.
  19.     temp_local_counts = {}
  20.     for i in range(l, r + 1):
  21.         val = a[i]
  22.         temp_local_counts[val] = temp_local_counts.get(val, 0) + 1
  23.  
  24.     for val, count in temp_local_counts.items():
  25.         if count % 2 != 0:
  26.             beauty += val
  27.     return beauty
  28.  
  29. def solve():
  30.     try:
  31.         line1 = sys.stdin.readline()
  32.         if not line1: return None
  33.         n, q = map(int, line1.split())
  34.         a = list(map(int, sys.stdin.readline().split()))
  35.     except (IOError, ValueError):
  36.         return None
  37.  
  38.     block_size = max(1, int(math.sqrt(n)))
  39.     num_blocks = (n + block_size - 1) // block_size
  40.  
  41.     get_block_id = lambda i: i // block_size
  42.     get_block_start = lambda block_idx: block_idx * block_size
  43.     get_block_end = lambda block_idx: min(n - 1, (block_idx + 1) * block_size - 1)
  44.  
  45.     block_beauty = [[0] * num_blocks for _ in range(num_blocks)]
  46.  
  47.     max_val_in_a = max(a) if a else 0
  48.  
  49.     for i in range(num_blocks):
  50.         for k in range(max_val_in_a + 1): temp_counts[k] = 0
  51.  
  52.         current_beauty = 0
  53.         for j in range(i, num_blocks):
  54.             start_k = get_block_start(j)
  55.             end_k = get_block_end(j)
  56.  
  57.             for k in range(start_k, end_k + 1):
  58.                 val = a[k]
  59.                 if temp_counts[val] % 2 != 0:
  60.                     current_beauty -= val
  61.                 else:
  62.                     current_beauty += val
  63.                 temp_counts[val] += 1
  64.             block_beauty[i][j] = current_beauty
  65.  
  66.     ans_prev = 0
  67.     answers = []
  68.  
  69.     for _ in range(q):
  70.         xp, yp = map(int, sys.stdin.readline().split())
  71.  
  72.         x = (xp - 1 + ans_prev) % n
  73.         y = (yp - 1 + ans_prev) % n
  74.  
  75.         l = min(x, y)
  76.         r = max(x, y)
  77.  
  78.         bl = get_block_id(l)
  79.         br = get_block_id(r)
  80.  
  81.         current_beauty = 0
  82.  
  83.         if bl == br:
  84.             current_beauty = calculate_beauty_direct(a, l, r)
  85.         else:
  86.             for k in range(max_val_in_a + 1): temp_counts[k] = 0
  87.  
  88.             if bl + 1 <= br - 1:
  89.                 current_beauty = block_beauty[bl + 1][br - 1]
  90.  
  91.                 l_full = get_block_start(bl + 1)
  92.                 r_full = get_block_end(br - 1)
  93.                 for k in range(l_full, r_full + 1):
  94.                     temp_counts[a[k]] += 1
  95.  
  96.             r_bl = get_block_end(bl)
  97.             for k in range(l, r_bl + 1):
  98.                 val = a[k]
  99.                 if temp_counts[val] % 2 != 0:
  100.                     current_beauty -= val
  101.                 else:
  102.                     current_beauty += val
  103.                 temp_counts[val] += 1
  104.  
  105.             l_br = get_block_start(br)
  106.             for k in range(l_br, r + 1):
  107.                 val = a[k]
  108.                 if temp_counts[val] % 2 != 0:
  109.                     current_beauty -= val
  110.                 else:
  111.                     current_beauty += val
  112.                 temp_counts[val] += 1
  113.  
  114.         answers.append(str(current_beauty))
  115.         ans_prev = current_beauty
  116.  
  117.     return " ".join(answers)
  118.  
  119. def main():
  120.     try:
  121.         t_line = sys.stdin.readline()
  122.         if not t_line: return
  123.         t = int(t_line)
  124.  
  125.         output_buffer = []
  126.         for _ in range(t):
  127.             result = solve()
  128.             if result is not None:
  129.                 output_buffer.append(result)
  130.  
  131.         print("\n".join(output_buffer))
  132.  
  133.     except (IOError, ValueError):
  134.         return
  135.  
  136. if __name__ == "__main__":
  137.     main()
Success #stdin #stdout 0.24s 17744KB
comments (?)
stdin 
3
11 4
1 1 2 2 3 3 3 2 2 1 1
7 10
5 11
8 6
2 8
6 2
1 3 2 3 4 3
1 6
1 4
3 6
3 3 3
1 1
1 2
3 1
2 2
2 3
3 3
stdout 
4 5 4 0
10 6
3 0 3 3 0 3
https://ideone.com/alMkLg
language:
Python 3 (python  3.12)
created:
2 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!