fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. struct SegmentTreeNode {
  8.     int start;
  9.     int end;
  10.     set<int> elements;
  11.     SegmentTreeNode* left;
  12.     SegmentTreeNode* right;
  13. };
  14.  
  15. SegmentTreeNode* buildSegmentTree(vector<int>& a, int start, int end) {
  16.     if (start > end) {
  17.         return nullptr;
  18.     }
  19.  
  20.     SegmentTreeNode* node = new SegmentTreeNode();
  21.     node->start = start;
  22.     node->end = end;
  23.     node->left = nullptr;
  24.     node->right = nullptr;
  25.  
  26.     if (start == end) {
  27.         node->elements.insert(a[start]);
  28.         return node;
  29.     }
  30.  
  31.     int mid = (start + end) / 2;
  32.     node->left = buildSegmentTree(a, start, mid);
  33.     node->right = buildSegmentTree(a, mid + 1, end);
  34.  
  35.     for (int element : node->left->elements) {
  36.         node->elements.insert(element);
  37.     }
  38.     for (int element : node->right->elements) {
  39.         node->elements.insert(element);
  40.     }
  41.  
  42.     return node;
  43. }
  44.  
  45. bool querySegmentTree(SegmentTreeNode* node, int l, int r, int x) {
  46.     if (node == nullptr) {
  47.         return false;
  48.     }
  49.  
  50.     if (l <= node->start && r >= node->end) {
  51.         return node->elements.count(x) > 0;
  52.     }
  53.  
  54.     if (l > node->end || r < node->start) {
  55.         return false;
  56.     }
  57.  
  58.     bool leftResult = querySegmentTree(node->left, l, r, x);
  59.     bool rightResult = querySegmentTree(node->right, l, r, x);
  60.  
  61.     return leftResult || rightResult;
  62. }
  63.  
  64. int main() {
  65.     //freopen("input.txt", "r", stdin);
  66.     //freopen("output.txt", "w", stdout);
  67.     int n, q;
  68.     cin >> n >> q;
  69.  
  70.     vector<int> a(n);
  71.     for (int i = 0; i < n; i++) {
  72.         cin >> a[i];
  73.     }
  74.  
  75.     SegmentTreeNode* root = buildSegmentTree(a, 0, n - 1);
  76.  
  77.     for (int i = 0; i < q; i++) {
  78.         int l, r, x;
  79.         cin >> l >> r >> x;
  80.  
  81.         bool result = querySegmentTree(root, l - 1, r - 1, x);
  82.         cout << (result ? "Yes" : "No") << endl;
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5424KB
comments (?)
stdin
copy 
6 4
1 2 3 4 5 6
1 2 1
3 4 2
1 6 7
2 5 3
stdout
copy 
Yes
No
No
Yes
https://ideone.com/16g2mc
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!