Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define endl "\n"
- using namespace std;
- using ll = long long;
- using ld = long double;
- using pii = pair<int, int>;
- constexpr int N = 1e5+5;
- struct V
- {
- int val;
- V* l;
- V* r;
- V(int v = 0, V* a = nullptr, V* b = nullptr) :
- val(v), l(a), r(b){};
- };
- using pv = V*;
- V buf[40*N];
- map<int, stack<int>> mp;
- pv ver[N], root = nullptr;
- int s = 0, n, val, ans, arr[N];
- string q;
- pv newV(int v = 0, pv l = nullptr, pv r = nullptr)
- {
- buf[s] = V(v, l, r);
- return &buf[s++];
- }
- int getans(pv v)
- {
- return v == nullptr ? 0 : v->val;
- }
- pv upd(int pos, int val, pv v = root, int l = 0, int r = n)
- {
- if (l+1 == r)
- return newV(val);
- int m = (l+r)>>1;
- pv tl = v == nullptr ? nullptr : v->l,
- tr = v == nullptr ? nullptr : v->r;
- if (pos < m)
- tl = upd(pos, val, tl, l, m);
- else tr = upd(pos, val, tr, m, r);
- return newV(getans(tl) + getans(tr), tl, tr);
- }
- int get (int val, pv v, int l = 0, int r = n)
- {
- if (l+1 == r)
- return l + val - getans(v);
- int m = (l+r)>>1;
- pv tl = v == nullptr ? nullptr : v->l,
- tr = v == nullptr ? nullptr : v->r;
- if (getans(tl) >= val)
- return get(val, tl, l, m);
- else
- return get(val - getans(tl), tr, m, r);
- }
- void Solve()
- {
- cin >> n;
- for (int i = 0; i < n; i++)
- {
- cin >> arr[i];
- mp[arr[i]].push(i);
- }
- for (int i = n - 1; i >= 0; i--)
- {
- upd(i, 1);
- if (i != mp[arr[i]].top())
- upd(mp[arr[i]].top(), 0), mp[arr[i]].pop();
- ver[i] = root;
- }
- for (int i = 1; i <= n; i++)
- {
- val = get(i, ver[1]);
- ans = 1;
- while(val < n)
- {
- val = get(i, ver[val+1]);
- ans++;
- }
- cout << ans << " ";
- }
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- Solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement