fork download 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. #define all(x) (x).begin(), (x).end()
  6. #define allr(x) (x).rbegin(), (x).rend()
  7. #define vec vector
  8. #define ar array
  9. #define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
  10. #ifdef _MSC_VER
  11. #define __builtin_popcount __popcnt
  12. #define __builtin_clz __lzcnt
  13. #endif
  14. int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
  15. int dy[] = { -1, 1, 0, 0, -1, 1, 1, -1 };
  16. mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
  17. ll rnd(ll a, ll b) {
  18.     return a + rng() % (b - a + 1);
  19. }
  20.  
  21. void file_f() {
  22. #pragma warning(disable:26451)
  23. #pragma warning(disable:6031)
  24. #ifndef ONLINE_JUDGE
  25.     freopen("in.txt", "r", stdin);
  26.     //freopen("out.txt", "w", stdout);
  27. #else
  28.     //freopen("army.in", "r", stdin);
  29.     //freopen("output.txt", "w", stdout);
  30. #endif
  31. }
  32.  
  33.  
  34. // m3ande4 fekra eh da bs it's working
  35. #define sim template < class c
  36. #define ris return * this
  37. #define dor > debug & operator <<
  38. #define eni(x) sim > typename \
  39.   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  40. sim > struct rge { c b, e; };
  41. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  42. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  43. sim > char dud(...);
  44. struct debug {
  45.     ~debug() { cerr << endl; }
  46.     eni(!= ) cerr << boolalpha << i; ris;
  47. }
  48. eni(== ) ris << range(begin(i), end(i));
  49. }
  50. sim, class b dor(pair < b, c > d) {
  51.     ris << "(" << d.first << ", " << d.second << ")";
  52. }
  53. sim dor(rge<c> d) {
  54.     *this << "[";
  55.     for (auto it = d.b; it != d.e; ++it)
  56.         *this << ", " + 2 * (it == d.b) << *it;
  57.     ris << "]";
  58. }
  59. };
  60. #define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  61. // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
  62. #define x_q {
  63.  
  64.  
  65.  
  66. struct segtree {
  67.  
  68.     int size = 0;
  69.     vector<ll> tree, mncount;
  70.  
  71.     void init(int n) {
  72.         size = 1;
  73.         while (size < n) size *= 2;
  74.         tree.resize(2 * size);
  75.         mncount.resize(2 * size);
  76.     }
  77.  
  78.     ll merge(ll x, ll y) {
  79.         return min(x, y);
  80.     }
  81.  
  82.     void build(const vector<int>& v) {
  83.         for (int i = 0; i < (int) v.size(); i++) {
  84.             tree[size + i] = v[i];
  85.             mncount[size + i] = 1;
  86.         }
  87.         for (int i = size - 1; i >= 1; i--) {
  88.             tree[i] = merge(
  89.                 tree[2 * i],
  90.                 tree[2 * i + 1]
  91.             );
  92.             if (tree[i] == tree[2 * i]) {
  93.                 mncount[i] += mncount[2 * i];
  94.             }
  95.             if (tree[i] == tree[2 * i + 1]) {
  96.                 mncount[i] += mncount[2 * i + 1];
  97.             }
  98.         }
  99.     }
  100.  
  101.  
  102.     ll query(int lqry, int rqry) {
  103.         return query(1, lqry, rqry, 0, size - 1);
  104.     }
  105.  
  106.     ll query(int i, int lqry, int rqry, int myl, int myr) {
  107.         if (myr < lqry || myl > rqry) return (ll) 2e9;
  108.         if (lqry <= myl && myr <= rqry) return tree[i];
  109.  
  110.         int mid = (myl + myr) / 2;
  111.         int f = merge(
  112.             query(2 * i    , lqry, rqry, myl    , mid),
  113.             query(2 * i + 1, lqry, rqry, mid + 1, myr)
  114.         );
  115.         return f;
  116.     }
  117.  
  118.     void upd(int i, int v) {
  119.         upd(1, i, i, 0, size - 1, v);
  120.     }
  121.  
  122.     void upd(int i, int lqry, int rqry, int myl, int myr, int v) {
  123.         if (myr < lqry || myl > rqry) return;
  124.         if (lqry <= myl && myr <= rqry) {
  125.             tree[i] = v;
  126.             return;
  127.         }
  128.  
  129.         int mid = (myl + myr) / 2;
  130.         upd(2 * i, lqry, rqry, myl, mid, v);
  131.         upd(2 * i + 1, lqry, rqry, mid + 1, myr, v);
  132.  
  133.         tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
  134.  
  135.         mncount[i] = 0;
  136.         if (tree[i] == tree[2 * i]) {
  137.             mncount[i] += mncount[2 * i];
  138.         }
  139.         if (tree[i] == tree[2 * i + 1]) {
  140.             mncount[i] += mncount[2 * i + 1];
  141.         }
  142.     }
  143.  
  144.     ll count(int lqry, int rqry, int mn) {
  145.         return count(1, lqry, rqry, 0, size - 1, mn);
  146.     }
  147.  
  148.     ll count(int i, int lqry, int rqry, int myl, int myr, int mn) {
  149.         if (myr < lqry || myl > rqry) return (ll)0;
  150.         if (lqry <= myl && myr <= rqry) {
  151.             if (tree[i] == mn) return mncount[i];
  152.             return 0;
  153.         }
  154.  
  155.         int mid = (myl + myr) / 2;
  156.         return count(2 * i,     lqry, rqry, myl,     mid, mn) +
  157.                count(2 * i + 1, lqry, rqry, mid + 1, myr, mn);
  158.     }
  159.  
  160. };
  161.  
  162.  
  163.  
  164.  
  165. void solve() {
  166.     int n, m;
  167.     cin >> n >> m;
  168.  
  169.     segtree st;
  170.     st.init(n);
  171.  
  172.     vector<int> v(n);
  173.     for (int i = 0; i < n; i++) {
  174.         cin >> v[i];
  175.     }
  176.     st.build(v);
  177.  
  178.     while (m--) {
  179.         int op = 2;
  180.         cin >> op;
  181.         if (op == 1) {
  182.             int i, v;
  183.             cin >> i >> v;
  184.             //i--;
  185.             st.upd(i, v);
  186.         }
  187.         else {
  188.             int l, r;
  189.             cin >> l >> r;
  190.             //l--, r--;
  191.             r--;
  192.             ll mn = st.query(l, r);
  193.             ll cnt = st.count(l, r, mn);
  194.             cout << mn << " " << cnt << '\n';
  195.         }
  196.     }
  197. }
  198.  
  199.  
  200.  
  201.  
  202.  
  203. int main() {
  204.     //file_f();
  205.     cin.tie(0); cin.sync_with_stdio(0);
  206.     //cout << setprecision(6) << fixed;
  207.  
  208.     int T = 1;// cin >> T;
  209.     for (int i = 1; i <= T; i++) {
  210.         solve();
  211.     }
  212. }
Success #stdin #stdout 0.01s 5412KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/DGgRr7
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

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!