fork(3) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <cmath>
  6. using namespace std;
  7. typedef long long int LL;
  8.  
  9. struct node{
  10. int l;
  11. int r;
  12. int id;
  13. }u[311111];
  14.  
  15. int z;
  16. bool cool(node a,node b)
  17. {
  18. if(a.l/z<b.l/z)
  19. return true;
  20. if(a.l/z>b.l/z)
  21. return false;
  22. return a.r<b.r;
  23. }
  24. int cnt[1111111];
  25. int ans[311111];
  26. int v[311111];
  27.  
  28. int main()
  29. {
  30.  
  31. //ios_base:: sync_with_stdio(false); cin.tie(0);
  32.  
  33.  
  34. // freopen("input.in","r",stdin);
  35.  
  36. int n;cin>>n;
  37. int fuk=0;
  38. z=sqrt(n);
  39. // vector<int>v(n);
  40.  
  41. for(int i=0;i<n;i++)
  42. scanf("%d",&v[i]);
  43.  
  44. int q;cin>>q;for(int i=0;i<q;i++)
  45. {
  46. int l,r;
  47. scanf("%d %d",&l,&r);
  48. node tmp;
  49. tmp.l=l-1;
  50. tmp.r=r-1;
  51. tmp.id=i;
  52. u[i]=tmp;
  53. }
  54.  
  55. sort(u,u+q,cool);
  56.  
  57. int st=0,e=0;fuk=1;cnt[v[0]]++;
  58.  
  59. for(int i=0;i<q;i++)
  60. {
  61. int l=u[i].l;
  62. int r=u[i].r;
  63. // cout<<l<<" "<<r<<" "<<st<<" "<<e<<" "<<fuk<<endl;
  64.  
  65. while(st<l)
  66. {
  67. cnt[v[st]]--;
  68. if(cnt[v[st]]==0)
  69. fuk--;
  70. st++;
  71. }
  72. while(st>l)
  73. {
  74. st--;
  75. cnt[v[st]]++;
  76. if(cnt[v[st]]==1)
  77. fuk++;
  78. }
  79. while(e<r)
  80. {
  81. e++;
  82. cnt[v[e]]++;
  83. if(cnt[v[e]]==1)
  84. fuk++;
  85. }
  86. while(e>r)
  87. {
  88. cnt[v[e]]--;
  89. if(cnt[v[e]]==0)
  90. fuk--;
  91. e--;
  92. }
  93. ans[u[i].id]=fuk;
  94. }
  95.  
  96. for(int i=0;i<q;i++)
  97. printf("%d\n",ans[i]);
  98.  
  99. return 0;
  100. }
  101.  
  102.  
  103.  
Time limit exceeded #stdin #stdout 5s 13888KB
stdin
Standard input is empty
stdout
Standard output is empty