fork download
copy 
  1. class FenwickTree:
  2.     def __init__(self, x):
  3.         self.bit = x
  4.         for i in range(len(x)):
  5.             j = i | (i + 1)
  6.             if j < len(x):
  7.                 x[j] += x[i]
  8.  
  9.     def update(self, idx, x):
  10.         while idx < len(self.bit):
  11.             self.bit[idx] += x
  12.             idx |= idx + 1
  13.  
  14.     def query(self, end):
  15.         x = 0
  16.         while end:
  17.             x += self.bit[end - 1]
  18.             end &= end - 1
  19.         return x
  20.  
  21. n = int(input())
  22.  
  23. arr = list(map(int, input().split()))
  24.  
  25. adds = [[] for _ in range(n)]
  26.  
  27. dels = [[] for _ in range(n)]
  28.  
  29. prev = {}
  30.  
  31. for i in range(n):
  32.     adds[prev.get(arr[i], -1) + 1].append(i)
  33.     dels[i].append(i)
  34.     prev[arr[i]] = i
  35.  
  36. q = int(input())
  37.  
  38. queries = [[] for _ in range(n)]
  39.  
  40. res = [-1] * q
  41.  
  42. for i in range(q):
  43.     l, r = map(int, input().split())
  44.     l -= 1
  45.     r -= 1
  46.     queries[l].append((r, i))
  47.  
  48. curr = FenwickTree([0] * (n + 1))
  49.  
  50. for i in range(n):
  51.     for l in adds[i]:
  52.         curr.update(l, 1)
  53.     for l, pos in queries[i]:
  54.         res[pos] = curr.query(l + 1)
  55.     for l in dels[i]:
  56.         curr.update(l, -1)
  57.  
  58. print(*res)
Success #stdin #stdout 0.03s 9636KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3 2 3
https://ideone.com/orQvki
DQUERY Python Solution
language:
Python 3 (python  3.9.5)
created:
1 year 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!