fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define N 30005
  5. vector<int> v[N];
  6. typedef pair<pair<int, int>,pair<int,int>> pi;
  7. vector<pi> pr;
  8. int tree[4*N]={0};
  9.  
  10. void update(int node,int st,int end,int x)
  11. {
  12. if(st==end)
  13. {
  14. tree[node]=1;
  15. return;
  16. }
  17. int m=(st+end)/2;
  18. if(st<=x && x<=m)
  19. update(2*node,st,m,x);
  20. else
  21. update(2*node+1,m+1,end,x);
  22. tree[node]=tree[2*node]+tree[2*node+1];
  23. }
  24.  
  25. int query(int node,int st,int end,int l,int r)
  26. {
  27. if(st>r || end<l)
  28. return 0;
  29. if(st>=l && end<=r)
  30. return tree[node];
  31.  
  32. int m=(st+end)/2;
  33. int p1=query(2*node,st,m,l,r);
  34. int p2=query(2*node+1,m+1,end,l,r);
  35. return p1+p2;
  36. }
  37.  
  38. bool comp(pi a,pi b)
  39. {
  40. return a.first.first<b.first.first;
  41. }
  42.  
  43. int main()
  44. {
  45. ios_base::sync_with_stdio(false);
  46. cin.tie(NULL);
  47.  
  48. int n;
  49. cin>>n;
  50.  
  51. vector<int> arr,a;
  52. for(int i=0;i<n;i++)
  53. {
  54. int x;
  55. cin>>x;
  56. arr.push_back(x);
  57. }
  58.  
  59. set<int> s;
  60. for(int i=0;i<n;i++)
  61. s.insert(arr[i]);
  62.  
  63. for(auto it=s.begin();it!=s.end();it++)
  64. {
  65. a.push_back(*it);
  66. }
  67.  
  68. for(int i=0;i<n;i++)
  69. {
  70. int ind=lower_bound(a.begin(),a.end(),arr[i])-a.begin();
  71. v[ind].push_back(i+1);
  72. }
  73.  
  74. int q;
  75. cin>>q;
  76.  
  77. for(int c=0;c<q;c++)
  78. {
  79. int i,j,k;
  80. cin>>i>>j>>k;
  81.  
  82. pr.push_back(make_pair(make_pair(k,c),make_pair(i,j)));
  83. }
  84. sort(pr.begin(),pr.end(),comp);
  85.  
  86. int ans[q];
  87. int mx=-1;
  88. for(int i=0;i<q;i++)
  89. {
  90. int l=pr[i].second.first;
  91. int r=pr[i].second.second;
  92. int k=lower_bound(a.begin(),a.end(),pr[i].first.first)-a.begin();
  93. int ind=pr[i].first.second;
  94. if(a[k]>pr[i].first.first)
  95. k--;
  96.  
  97. while(mx<=k)
  98. {
  99. if(mx>=0)
  100. {
  101. for(auto num:v[mx])
  102. {
  103. update(1,1,n,num);
  104. }
  105. }
  106. mx++;
  107. }
  108. ans[ind]=r-l+1-query(1,1,n,l,r);
  109. }
  110.  
  111. for(int i=0;i<q;i++)
  112. cout<<ans[i]<<endl;
  113. }
Success #stdin #stdout 0s 4484KB
stdin
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 
stdout
2
0
3