Language: C++


struct SuccinctIndexableDictionary
{
  size_t length;
  size_t blocks;
  vector< unsigned > bit, sum;
 
  SuccinctIndexableDictionary()
  {
  }
 
  SuccinctIndexableDictionary(size_t _length)
  {
    length = _length;
    blocks = (length + 31) >> 5;
    bit.assign(blocks, 0U);
    sum.assign(blocks, 0U);
  }
 
  void set(int k)
  {
    bit[k >> 5] |= 1U << (k & 31);
  }
 
  void build()
  {
    sum[0] = 0U;
    for(int i = 1; i < blocks; i++) {
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }
 
  bool operator[](int k) const
  {
    return (bool((bit[k >> 5] >> (k & 31)) & 1));
  }
 
  int rank(int k)
  {
    return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
  }
 
  int rank(bool val, int k)
  {
    return (val ? rank(k) : k - rank(k));
  }
 
  int select(bool val, int k)
  {
    if(k < 0 || rank(val, length) <= k) return (-1);
    int low = 0, high = length;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(rank(val, mid) >= k + 1) high = mid;
      else low = mid;
    }
    return (high - 1);
  }
 
  int select(bool val, int i, int l)
  {
    return select(val, i + rank(val, l));
  }
};
 
template<class T, int MAXLOG>
struct WaveletMatrix
{
  size_t length;
  SuccinctIndexableDictionary matrix[MAXLOG];
  int zs[MAXLOG];
  int buff1[MAXLOG], buff2[MAXLOG];
 
  void max_dfs(int d, int l, int r, int& k, T val, vector< T >& vs)
  {
    if(l >= r || !k) return;
    if(d == MAXLOG) {
      while(l++ < r && k > 0) vs.push_back(val), k--;
      return;
    }
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    max_dfs(d + 1, lc + zs[d], rc + zs[d], k, 1ULL << (MAXLOG - d - 1) | val, vs);
    max_dfs(d + 1, l - lc, r - rc, k, val, vs);
  }
 
  T max_dfs(int d, int l, int r, T val, T a, T b)
  {
    if(r - l <= 0 || val >= b) return -1;
    if(d == MAXLOG) return val >= a ? val : -1;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    T ret = max_dfs(d + 1, lc + zs[d], rc + zs[d], 1ULL << (MAXLOG - d - 1) | val, a, b);
    if(~ret) return ret;
    return max_dfs(d + 1, l - lc, r - rc, val, a, b);
  }
 
  int freq_dfs(int d, int l, int r, T val, T a, T b)
  {
    if(l == r) return 0;
    if(d == MAXLOG) return (a <= val && val < b) ? r - l : 0;
    T nv = 1ULL << (MAXLOG - d - 1) | val, nnv = ((1ULL << (MAXLOG - d - 1)) - 1) | nv;
    if(nnv < a || b <= val) return 0;
    if(a <= val && nnv < b) return r - l;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    return freq_dfs(d + 1, l - lc, r - rc, val, a, b) +
           freq_dfs(d + 1, lc + zs[d], rc + zs[d], nv, a, b);
  }
 
  void list_dfs(int d, int l, int r, T val, T a, T b, vector< pair< T, int>>& vs)
  {
    if(val >= b || r - l <= 0) return;
    if(d == MAXLOG) {
      if(a <= val) vs.push_back(make_pair(val, r - l));
      return;
    }
    T nv = val | (1LL << (MAXLOG - d - 1)), nnv = nv | (((1LL << (MAXLOG - d - 1)) - 1));
    if(nnv < a) return;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    list_dfs(d + 1, l - lc, r - rc, val, a, b, vs);
    list_dfs(d + 1, lc + zs[d], rc + zs[d], nv, a, b, vs);
  }
 
 
  WaveletMatrix(vector< T > data)
  {
    length = data.size();
    vector< T > l(length), r(length);
    for(int depth = 0; depth < MAXLOG; depth++) {
      matrix[depth] = SuccinctIndexableDictionary(length + 1);
      int left = 0, right = 0;
      for(int i = 0; i < length; i++) {
        bool k = (data[i] >> (MAXLOG - depth - 1)) & 1;
        if(k) r[right++] = data[i], matrix[depth].set(i);
        else l[left++] = data[i];
      }
      zs[depth] = left;
      matrix[depth].build();
      swap(l, data);
      for(int i = 0; i < right; i++) data[left + i] = r[i];
    }
  }
 
  T access(int k)
  {
    int ret = 0;
    bool bit;
    for(int depth = 0; depth < MAXLOG; depth++) {
      bit = matrix[depth][k];
      ret = (ret << 1) | bit;
      k = matrix[depth].rank(bit, k) + zs[depth] * bit;
    }
    return (ret);
  }
 
  int rank(T val, int k)
  {
    int l = 0, r = k;
    for(int depth = 0; depth < MAXLOG; depth++) {
      buff1[depth] = l, buff2[depth] = r;
      bool bit = (val >> (MAXLOG - depth - 1)) & 1;
      l = matrix[depth].rank(bit, l) + zs[depth] * bit;
      r = matrix[depth].rank(bit, r) + zs[depth] * bit;
    }
    return (r - l);
  }
 
  int select(T val, int kth)
  {
    rank(val, length);
    for(int depth = MAXLOG - 1; depth >= 0; depth--) {
      bool bit = (val >> (MAXLOG - depth - 1)) & 1;
      kth = matrix[depth].select(bit, kth, buff1[depth]);
      if(kth >= buff2[depth] || kth < 0) return (-1);
      kth -= buff1[depth];
    }
    return (kth);
  }
 
  int select(T val, int k, int l)
  {
    return (select(val, k + rank(val, l)));
  }
 
 
  int quantile(int left, int right, int kth)
  {
    if(right - left <= kth || kth < 0) return (-1);
    T ret = 0;
    for(int depth = 0; depth < MAXLOG; depth++) {
      int l = matrix[depth].rank(1, left);
      int r = matrix[depth].rank(1, right);
      if(r - l > kth) {
        left = l + zs[depth];
        right = r + zs[depth];
        ret |= 1ULL << (MAXLOG - depth - 1);
      } else {
        kth -= r - l;
        left -= l;
        right -= r;
      }
    }
    return (ret);
  }
 
  vector< T > topk(int l, int r, int k)
  {
    if(r - l < k) k = r - l;
    if(k < 0) return (vector< T >());
    vector< T > ret;
    max_dfs(0, l, r, k, 0, ret);
    return (ret);
  }
 
  vector< pair< T, int > > freq_list(int l, int r, T a, T b)
  {
    vector< pair< T, int > > ret;
    list_dfs(0, l, r, 0, a, b, ret);
    return (ret);
  }
 
  vector< pair< int, T > > get_rect(int l, int r, T a, T b)
  {
    vector< pair< T, int > > res = freq_list(l, r, a, b);
    vector< pair< int, T > > ret;
    for(auto& e : res) {
      for(int i = 0; i < e.second; i++) {
        ret.emplace_back(select(e.first, i, l), e.first);
      }
    }
    return (ret);
  }
 
  int rangefreq(int left, int right, T lower, T upper)
  {
    return (freq_dfs(0, left, right, 0, lower, upper));
  }
};
int main()
{
  int N, Q;
  scanf("%d", &N);
  vector< int > X(N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &X[i]);
    X[i] += 1e8;
  }
  WaveletMatrix< int, 29 > matrix(X);
  scanf("%d", &Q);
  while(Q--) {
    int L, R, E;
    scanf("%d %d %d", &L, &R, &E);
    --L, --R;
    printf("%d\n", (R - L + 1) - matrix.rangefreq(L, R + 1, min(X[L], X[R]) - E, max(X[L], X[R]) + E + 1));
  }
}

Compiler output:
a.cc:4:3: error: 'size_t' does not name a type
    4 |   size_t length;
      |   ^~~~~~
a.cc:1:1: note: 'size_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
  +++ |+#include <cstddef>
    1 | 
a.cc:5:3: error: 'size_t' does not name a type
    5 |   size_t blocks;
      |   ^~~~~~
a.cc:5:3: note: 'size_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:6:3: error: 'vector' does not name a type
    6 |   vector< unsigned > bit, sum;
      |   ^~~~~~
a.cc:12:37: error: expected ')' before '_length'
   12 |   SuccinctIndexableDictionary(size_t _length)
      |                              ~      ^~~~~~~~
      |                                     )
a.cc: In member function 'void SuccinctIndexableDictionary::set(int)':
a.cc:22:5: error: 'bit' was not declared in this scope
   22 |     bit[k >> 5] |= 1U << (k & 31);
      |     ^~~
a.cc: In member function 'void SuccinctIndexableDictionary::build()':
a.cc:27:5: error: 'sum' was not declared in this scope
   27 |     sum[0] = 0U;
      |     ^~~
a.cc:28:24: error: 'blocks' was not declared in this scope
   28 |     for(int i = 1; i < blocks; i++) {
      |                        ^~~~~~
a.cc:29:48: error: 'bit' was not declared in this scope
   29 |       sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
      |                                                ^~~
a.cc: In member function 'bool SuccinctIndexableDictionary::operator[](int) const':
a.cc:35:19: error: 'bit' was not declared in this scope
   35 |     return (bool((bit[k >> 5] >> (k & 31)) & 1));
      |                   ^~~
a.cc: In member function 'int SuccinctIndexableDictionary::rank(int)':
a.cc:40:13: error: 'sum' was not declared in this scope
   40 |     return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
      |             ^~~
a.cc:40:46: error: 'bit' was not declared in this scope
   40 |     return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
      |                                              ^~~
a.cc: In member function 'int SuccinctIndexableDictionary::select(bool, int)':
a.cc:50:27: error: 'length' was not declared in this scope
   50 |     if(k < 0 || rank(val, length) <= k) return (-1);
      |                           ^~~~~~
a.cc:51:25: error: 'length' was not declared in this scope
   51 |     int low = 0, high = length;
      |                         ^~~~~~
a.cc: At global scope:
a.cc:69:3: error: 'size_t' does not name a type
   69 |   size_t length;
      |   ^~~~~~
a.cc:69:3: note: 'size_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:74:52: error: 'vector' has not been declared
   74 |   void max_dfs(int d, int l, int r, int& k, T val, vector< T >& vs)
      |                                                    ^~~~~~
a.cc:74:58: error: expected ',' or '...' before '<' token
   74 |   void max_dfs(int d, int l, int r, int& k, T val, vector< T >& vs)
      |                                                          ^
a.cc:108:55: error: 'vector' has not been declared
  108 |   void list_dfs(int d, int l, int r, T val, T a, T b, vector< pair< T, int>>& vs)
      |                                                       ^~~~~~
a.cc:108:61: error: expected ',' or '...' before '<' token
  108 |   void list_dfs(int d, int l, int r, T val, T a, T b, vector< pair< T, int>>& vs)
      |                                                             ^
a.cc:123:23: error: expected ')' before '<' token
  123 |   WaveletMatrix(vector< T > data)
      |                ~      ^
      |                       )
a.cc:204:3: error: 'vector' does not name a type
  204 |   vector< T > topk(int l, int r, int k)
      |   ^~~~~~
a.cc:213:3: error: 'vector' does not name a type
  213 |   vector< pair< T, int > > freq_list(int l, int r, T a, T b)
      |   ^~~~~~
a.cc:220:3: error: 'vector' does not name a type
  220 |   vector< pair< int, T > > get_rect(int l, int r, T a, T b)
      |   ^~~~~~
a.cc: In member function 'void WaveletMatrix<T, MAXLOG>::max_dfs(int, int, int, int&, T, int)':
a.cc:78:31: error: 'vs' was not declared in this scope; did you mean 'zs'?
   78 |       while(l++ < r && k > 0) vs.push_back(val), k--;
      |                               ^~
      |                               zs
a.cc:82:79: error: 'vs' was not declared in this scope; did you mean 'zs'?
   82 |     max_dfs(d + 1, lc + zs[d], rc + zs[d], k, 1ULL << (MAXLOG - d - 1) | val, vs);
      |                                                                               ^~
      |                                                                               zs
a.cc: In member function 'void WaveletMatrix<T, MAXLOG>::list_dfs(int, int, int, T, T, T, int)':
a.cc:112:20: error: 'vs' was not declared in this scope; did you mean 'zs'?
  112 |       if(a <= val) vs.push_back(make_pair(val, r - l));
      |                    ^~
      |                    zs
a.cc:118:48: error: 'vs' was not declared in this scope; did you mean 'zs'?
  118 |     list_dfs(d + 1, l - lc, r - rc, val, a, b, vs);
      |                                                ^~
      |                                                zs
a.cc: In member function 'int WaveletMatrix<T, MAXLOG>::select(T, int)':
a.cc:168:15: error: 'length' was not declared in this scope
  168 |     rank(val, length);
      |               ^~~~~~
a.cc: In function 'int main()':
a.cc:240:3: error: 'scanf' was not declared in this scope
  240 |   scanf("%d", &N);
      |   ^~~~~
a.cc:241:3: error: 'vector' was not declared in this scope
  241 |   vector< int > X(N);
      |   ^~~~~~
a.cc:241:11: error: expected primary-expression before 'int'
  241 |   vector< int > X(N);
      |           ^~~
a.cc:243:18: error: 'X' was not declared in this scope
  243 |     scanf("%d", &X[i]);
      |                  ^
a.cc:246:35: error: 'X' was not declared in this scope
  246 |   WaveletMatrix< int, 29 > matrix(X);
      |                                   ^
a.cc:252:61: error: 'min' was not declared in this scope; did you mean 'main'?
  252 |     printf("%d\n", (R - L + 1) - matrix.rangefreq(L, R + 1, min(X[L], X[R]) - E, max(X[L], X[R]) + E + 1));
      |                                                             ^~~
      |                                                             main
a.cc:252:82: error: 'max' was not declared in this scope
  252 |     printf("%d\n", (R - L + 1) - matrix.rangefreq(L, R + 1, min(X[L], X[R]) - E, max(X[L], X[R]) + E + 1));
      |                                                                                  ^~~
a.cc:252:5: error: 'printf' was not declared in this scope
  252 |     printf("%d\n", (R - L + 1) - matrix.rangefreq(L, R + 1, min(X[L], X[R]) - E, max(X[L], X[R]) + E + 1));
      |     ^~~~~~
a.cc:1:1: note: 'printf' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'
  +++ |+#include <cstdio>
    1 |