fork download
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6.  
  7.  
  8. class SqrtDecomposition {
  9.  
  10. int size, blockSize, blocksCount;
  11. vector<int> array;
  12. vector< vector<int> > blocks;
  13.  
  14. public:
  15.  
  16. SqrtDecomposition(const vector<int> &a) {
  17. array = a;
  18. size = a.size();
  19. blockSize = sqrt(size);
  20. blocksCount = size / blockSize + (size % blockSize ? 1 : 0);
  21. blocks.resize(blocksCount);
  22. for (int i = 0; i < size; i++)
  23. blocks[i / blockSize].push_back(a[i]);
  24. for (int i = 0; i < blocksCount; i++)
  25. sort(blocks[i].begin(), blocks[i].end());
  26. }
  27.  
  28. int query(int l, int r, int k) const {
  29. int res = 0;
  30. while (l <= r && l % blockSize != 0)
  31. res += array[l++] > k;
  32. while (l <= r && r % blockSize != blockSize - 1)
  33. res += array[r--] > k;
  34. if (l <= r)
  35. for (l /= blockSize, r /= blockSize; l <= r; l++)
  36. res += blocks[l].end() - upper_bound(blocks[l].begin(), blocks[l].end(), k);
  37. return res;
  38. }
  39.  
  40. };
  41.  
  42.  
  43. int main() {
  44. int aSize;
  45. scanf("%d", &aSize);
  46.  
  47. vector<int> a(aSize);
  48. for (int i = 0; i < aSize; i++)
  49. scanf("%d", &a[i]);
  50.  
  51. SqrtDecomposition sd(a);
  52.  
  53. int queriesCount;
  54. scanf("%d", &queriesCount);
  55.  
  56. for (int i = 0; i < queriesCount; i++) {
  57. int l, r, k;
  58. scanf("%d%d%d", &l, &r, &k);
  59. printf("%d\n", sd.query(l - 1, r - 1, k));
  60. }
  61. }
Success #stdin #stdout 0s 3480KB
stdin
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 
stdout
2
0
3