fork(1) download
  1. from sys import stdin,stdout
  2. from collections import *
  3. from math import *
  4. st=lambda:list(stdin.readline().strip())
  5. li=lambda:list(map(int,stdin.readline().split()))
  6. mp=lambda:map(int,stdin.readline().split())
  7. inp=lambda:int(stdin.readline())
  8. pr=lambda n: stdout.write(str(n)+"\n")
  9.  
  10. mod=1000000007
  11. INF=float('inf')
  12. d={}
  13.  
  14. length=0
  15.  
  16. def ADD(x):
  17. global length
  18. if x not in d:
  19. length+=1
  20. d[x]=1
  21. else:
  22. d[x]+=1
  23.  
  24. def REMOVE(x):
  25. global length
  26. if d[x]==1:
  27. length-=1
  28. d.pop(x)
  29. else:
  30. d[x]-=1
  31.  
  32.  
  33.  
  34. def solve():
  35. n,q=mp()
  36. l=li()
  37. query=[li()+[i] for i in range(q)]
  38. query.sort(key=lambda x:(x[0],x[1]))
  39. curL,curR=0,-1
  40. ans=[0 for i in range(q)]
  41. for Q in query:
  42. left,right,ind=Q
  43. left-=1
  44. right-=1
  45.  
  46. while curL>left:
  47. curL-=1
  48. ADD(l[curL])
  49.  
  50. while curR<right:
  51. curR+=1
  52. ADD(l[curR])
  53.  
  54. while curL<left:
  55. REMOVE(l[curL])
  56. curL+=1
  57.  
  58. while curR>right:
  59. REMOVE(l[curR])
  60. curR-=1
  61.  
  62. ans[ind]=length
  63.  
  64. print('\n'.join(map(str,ans)))
  65.  
  66.  
  67.  
  68. for _ in range(1):
  69. solve()
  70.  
Success #stdin #stdout 0.02s 9396KB
stdin
10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8
stdout
1
2
2
1
2
2
6
3
3
3