Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define fi first
- #define se second
- struct segtree
- {
- ll size;
- vector<pair<ll, ll>> val;
- void init(ll n)
- {
- size = 1;
- while (size < n)
- {
- size *= 2;
- }
- pair<ll, ll> p = {1e18, 0};
- val.assign(2 * size, p);
- }
- void build(vector<ll> &a, ll x, ll lx, ll rx)
- {
- if (rx - lx == 1)
- {
- if (lx < a.size())
- {
- val[x] = {a[lx], 1};
- }
- }
- else
- {
- ll m = (lx + rx) / 2;
- build(a, 2 * x + 1, lx, m);
- build(a, 2 * x + 2, m, rx);
- auto pl = val[2 * x + 1], pr = val[2 * x + 2];
- if (pl.fi < pr.fi)
- {
- val[x] = pl;
- }
- else if (pl.fi > pr.fi)
- {
- val[x] = pr;
- }
- else
- {
- val[x] = {pl.fi, pr.se + pl.se};
- }
- }
- }
- void build(vector<ll> &a)
- {
- build(a, 0, 0, size);
- }
- void set(ll i, ll v, ll x, ll lx, ll rx)
- {
- if (rx - lx == 1)
- {
- val[x] = {v, 1};
- return;
- }
- ll m = (lx + rx) / 2;
- if (i < m)
- {
- set(i, v, 2 * x + 1, lx, m);
- }
- else
- {
- set(i, v, 2 * x + 2, m, rx);
- }
- auto pl = val[2 * x + 1], pr = val[2 * x + 2];
- if (pl.fi < pr.fi)
- {
- val[x] = pl;
- }
- else if (pl.fi > pr.fi)
- {
- val[x] = pr;
- }
- else
- {
- val[x] = {pl.fi, pr.se + pl.se};
- }
- }
- void set(ll i, ll v)
- {
- set(i, v, 0, 0, size);
- }
- pair<ll, ll> calc(ll l, ll r, ll x, ll lx, ll rx)
- {
- if (lx >= r || rx <= l)
- {
- pair<ll, ll> p = {1e18, 1};
- return p;
- }
- if (l <= lx && rx <= r)
- {
- return val[x];
- }
- ll m = (lx + rx) / 2;
- auto pl = calc(l, r, 2 * x + 1, lx, m);
- auto pr = calc(l, r, 2 * x + 2, m, rx);
- if (pl.fi < pr.fi)
- {
- return pl;
- }
- else if (pl.fi > pr.fi)
- {
- return pr;
- }
- else
- {
- return {pl.fi, pr.se + pl.se};
- }
- }
- pair<ll, ll> calc(ll l, ll r)
- {
- return calc(l, r, 0, 0, size);
- }
- };
- int main()
- {
- int n, m;
- cin >> n >> m;
- segtree st;
- vector<ll> a(n);
- st.init(n);
- for (ll i = 0; i < n; i++)
- {
- cin >> a[i];
- // st.set(i, a[i]);
- }
- st.build(a);
- for (ll q = 0; q < m; q++)
- {
- ll op;
- cin >> op;
- if (op == 1)
- {
- ll i, v;
- cin >> i >> v;
- st.set(i, v);
- }
- else
- {
- ll l, r;
- cin >> l >> r;
- auto p = st.calc(l, r);
- cout << p.fi << " " << p.se << "\n";
- }
- }
- }
Add Comment
Please, Sign In to add comment