fork download 
  1. from collections import defaultdict
  2.  
  3. class FenwickTree:
  4.     def __init__(self, x):
  5.         self.bit = x
  6.         for i in range(len(x)):
  7.             j = i | (i + 1)
  8.             if j < len(x):
  9.                 x[j] += x[i]
  10.  
  11.     def update(self, idx, x):
  12.         while idx < len(self.bit):
  13.             self.bit[idx] += x
  14.             idx |= idx + 1
  15.  
  16.     def query(self, end):
  17.         x = 0
  18.         while end:
  19.             x += self.bit[end - 1]
  20.             end &= end - 1
  21.         return x
  22.  
  23. class Seg:
  24.     def __init__(self, n):
  25.         N = 1
  26.         while N < n:
  27.             N <<= 1
  28.         self.N = N
  29.         self.t = [-1] * (2 * N)
  30.  
  31.     def set(self, i, v):
  32.         i += self.N
  33.         self.t[i] = v
  34.         i //= 2
  35.         while i:
  36.             a = self.t[2 * i]
  37.             b = self.t[2 * i + 1]
  38.             self.t[i] = a if a > b else b
  39.             i //= 2
  40.  
  41.     def prefmax(self, r):
  42.         l = self.N
  43.         r = r + self.N + 1
  44.         res = -1
  45.         while l < r:
  46.             if l & 1:
  47.                 v = self.t[l]
  48.                 if v > res: res = v
  49.                 l += 1
  50.             if r & 1:
  51.                 r -= 1
  52.                 v = self.t[r]
  53.                 if v > res: res = v
  54.             l //= 2
  55.             r //= 2
  56.         return res
  57.  
  58. n = int(input())
  59. arr = list(map(int, input().split()))
  60.  
  61. pos = defaultdict(list)
  62. for i, v in enumerate(arr):
  63.     pos[v].append(i)
  64.  
  65. ok = [-1] * n
  66. for v, lst in pos.items():
  67.     m = len(lst)
  68.     if m == 1:
  69.         ok[lst[0]] = n - 1
  70.         continue
  71.     d = [lst[i + 1] - lst[i] for i in range(m - 1)]
  72.     r = [0] * (m - 1)
  73.     r[m - 2] = m - 2
  74.     for i in range(m - 3, -1, -1):
  75.         if d[i] == d[i + 1]:
  76.             r[i] = r[i + 1]
  77.         else:
  78.             r[i] = i
  79.     for t in range(m):
  80.         if t == m - 1:
  81.             reach_idx = t
  82.         else:
  83.             reach_idx = r[t] + 1
  84.         if reach_idx + 1 < m:
  85.             nxt = lst[reach_idx + 1]
  86.         else:
  87.             nxt = n
  88.         ok[lst[t]] = nxt - 1
  89.  
  90. adds = [[] for _ in range(n)]
  91. dels = [[] for _ in range(n)]
  92. prev = {}
  93. for i in range(n):
  94.     adds[prev.get(arr[i], -1) + 1].append(i)
  95.     dels[i].append(i)
  96.     prev[arr[i]] = i
  97.  
  98. q = int(input())
  99. queries = [[] for _ in range(n)]
  100. for i in range(q):
  101.     l, r = map(int, input().split())
  102.     l -= 1
  103.     r -= 1
  104.     queries[l].append((r, i))
  105.  
  106. bit = FenwickTree([0] * (n + 1))
  107. seg = Seg(n)
  108. res = [0] * q
  109.  
  110. for i in range(n):
  111.     for p in adds[i]:
  112.         bit.update(p, 1)
  113.         seg.set(p, ok[p])
  114.     for r, idx in queries[i]:
  115.         distinct = bit.query(r + 1)
  116.         pm = seg.prefmax(r)
  117.         add = 0 if pm >= r else 1
  118.         res[idx] = distinct + add
  119.     for p in dels[i]:
  120.         bit.update(p, -1)
  121.         seg.set(p, -1)
  122.  
  123. print("\n".join(map(str, res)))
Runtime error #stdin #stdout #stderr 0.92s 37192KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Traceback (most recent call last):
  File "./prog.py", line 58, in <module>
EOFError: EOF when reading a line
https://ideone.com/BIfsIt
language:
Python 3 (python  3.12)
created:
101 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!