Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Segment Tree

gerkulesov Apr 5th, 2020 146 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. pair <int,int> combine(pair<int,int> a, pair<int,int> b) {
  6.     if (a.first < b.first)
  7.         return a;
  8.     if (a.first > b.first)
  9.         return b;
  10.     return {a.first, a.second + b.second};
  11. }
  12.  
  13. void build(vector <int> &a, vector <pair<int,int> > &tree, int v, int sl, int sr) {
  14.     if (sl == sr)
  15.         tree[v] = {a[sl], 1}; /// make_pair(first, second)
  16.     else {
  17.         int sm = (sl + sr)/2;
  18.         build(a, tree, 2*v, sl, sm);
  19.         build(a, tree, 2*v+1, sm+1, sr);
  20.         tree[v] = combine(tree[2*v], tree[2*v+1]);
  21.     }
  22.     return;
  23. }
  24.  
  25. void update(vector <pair<int,int> > &tree, int v, int sl, int sr, int idx, int val) {
  26.     if (sl == sr)
  27.         tree[v] = {val, 1};
  28.     else {
  29.         int sm = (sl + sr)/2;
  30.         if (idx <= sm) {
  31.             update(tree, 2*v, sl, sm, idx, val);
  32.         }
  33.         else {
  34.             update(tree, 2*v+1, sm+1, sr, idx, val);
  35.         }
  36.         tree[v] = combine(tree[2*v], tree[2*v+1]);
  37.     }
  38.     return;
  39. }
  40.  
  41. pair <int,int> get_min(vector <pair<int,int> > &tree, int v, int sl, int sr, int l, int r) {
  42.     if (l > r)
  43.         return {INT_MAX, 0};
  44.     if (sl == l && sr == r)
  45.         return tree[v];
  46.     else {
  47.         int sm = (sl + sr)/2;
  48.         return combine(get_min(tree, 2*v, sl, sm, l, min(sm,r)),
  49.                get_min(tree, 2*v+1, sm+1, sr, max(sm+1,l), r));
  50.     }
  51. }
  52.  
  53. int main()
  54. {
  55.     int n;
  56.     cin >> n;
  57.     vector <int> a(n);
  58.     for (int i=0; i<n; i++)
  59.         cin >> a[i];
  60.  
  61.     vector <pair<int,int> > tree(4*n);
  62.     build(a, tree, 1, 0, n-1);
  63.  
  64.     int l, r;
  65.     while (true) {
  66.         cin >> l >> r;
  67.         pair <int,int> ans;
  68.         ans = get_min(tree, 1, 0, n-1, l, r);
  69.         cout << ans.first << " " << ans.second << endl;
  70.     }
  71.  
  72.     return 0;
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top