Algo Experts Round #1 G-masala

Bu merge sort tree ni oddiy misoli edi. Merge sort tree haqida shu havola https://wiki.algocode.ru/index.php?title=Merge_sort_tree orqali toliq malumot olishingiz mumkin

#include <bits/stdc++.h>
using namespace std;

struct MergeSortTree
{
 vector<vector<int>> tree;
 int sz;
 typedef vector<int> T;
  void combine(T &parent, T &left_child, T &right_child)
 {
  int i=0, j=0, n=left_child.size();
  while(i<n && j<n)
  {
   if (left_child[i]>right_child[j])
parent.push_back(right_child[j++]);
   else parent.push_back(left_child[i++]);
  }
  while(i<n) parent.push_back(left_child[i++]);
  while(j<n) parent.push_back(right_child[j++]);
  
 }
 
 void build(T &a, int x, int lx, int rx)
 {
  if (rx==lx+1)
  {
   tree[x].resize(1);
   if (lx<a.size()) tree[x][0]=a[lx];
   else tree[x][0]=INT_MAX;
  }
  else
  {
   int m = lx+rx>>1;
   build(a, x*2+1, lx, m);
   build(a, x*2+2, m, rx);
   combine(tree[x], tree[2*x+1], tree[2*x+2]); 
  }
 }

 void build(vector<int> &a)
 {
  init(a.size());
  build(a, 0, 0, sz);
 }

 int get(int l, int r, int v, int u, int x, int lx, int rx)
 {
  if (r<=lx || rx<=l) return 0;
  if (l<=lx && rx<=r) 
  {
   return upper_bound(tree[x].begin(), tree[x].end(), u) - lower_bound(tree[x].begin(), tree[x].end(), v);
  }
  int m = lx+rx>>1;
  return get(l, r, v, u, x*2+1, lx, m)+get(l, r, v, u, x*2+2, m, rx);
 }

 int get(int l, int r, int x, int y)
 {
  return get(l, r, x, y, 0, 0, sz);
 }
 
 void init(int n)
 {
  sz=1;
  while(sz<n) sz *= 2;
  tree.resize(2*sz-1);
 }
};


signed main()
{
    ios::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 MergeSortTree tree;
 int n, q;
 cin >> n >> q;
 vector<int> v(n);
 for(int &i: v) cin >> i;
 tree.build(v);
 for(int i=0; i<q; ++i)
 {
  int l, r, x, y;
  cin >> l >> r >> x >> y;
  l--;
  cout << tree.get(l, r, x, y) << "\n";
 }
 return 0;
}