Advertisement
Josif_tepe

Untitled

May 10th, 2023
697
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. const int maxn = 1e5 + 10;
  6.  
  7. vector<int> segment_tree[3 * maxn];
  8. int arr[maxn];
  9. void build(int L, int R, int position) {
  10.     if(L == R) {
  11.         segment_tree[position].push_back(arr[L]);
  12.     }
  13.     else {
  14.         int mid = (L + R) / 2;
  15.         build(L, mid, 2 * position);
  16.         build(mid + 1, R, 2 * position + 1);
  17.         merge(segment_tree[2 * position].begin(), segment_tree[2 * position].end(), segment_tree[2 * position + 1].begin(), segment_tree[2 * position + 1].end(), back_inserter(segment_tree[position]));
  18.     }
  19. }
  20. int query(int L, int R, int position, int i, int j, int x) {
  21.     // L  R i L R j L R
  22.     if(i <= L and R <= j) {
  23.         int idx = lower_bound(segment_tree[position].begin(), segment_tree[position].end(), x) - segment_tree[position].begin();
  24.         if(idx >= 0 and idx < segment_tree[position].size()) {
  25.             if(segment_tree[position][idx] == x) {
  26.                 return 1;
  27.             }
  28.         }
  29.         return 0;
  30.     }
  31.     if(R < i or j < L) {
  32.         return 0;
  33.     }
  34.     int mid = (L + R) / 2;
  35.     return max(query(L, mid, 2 * position, i, j, x), query(mid + 1, R, 2 * position + 1, i, j, x));
  36. }
  37. int main() {
  38.     ios_base::sync_with_stdio(false);
  39.     int n;
  40.     cin >> n;
  41.     for(int i = 0; i < n; i++) {
  42.         cin >> arr[i];
  43.     }
  44.     build(0, n, 1);
  45.    
  46.     while(true) {
  47.         int i, j, x;
  48.         cin >> i >> j >> x;
  49.         cout << query(0, n, 1, i - 1, j - 1, x) << endl;
  50.     }
  51.     return 0;
  52. }
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement