Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class SegmentTree {
- public:
- vector<long long> tree, lazy;
- int n;
- SegmentTree(int size) {
- n = size;
- tree.assign(4 * n, 0);
- lazy.assign(4 * n, 0);
- }
- void push(int v) {
- if (lazy[v]) {
- tree[2 * v] += lazy[v];
- tree[2 * v + 1] += lazy[v];
- lazy[2 * v] += lazy[v];
- lazy[2 * v + 1] += lazy[v];
- lazy[v] = 0;
- }
- }
- void update(int v, int tl, int tr, int l, int r, long long add_val) {
- if (l > r)
- return;
- if (tl == l && tr == r) {
- tree[v] += add_val;
- lazy[v] += add_val;
- } else {
- push(v);
- int tm = (tl + tr) / 2;
- update(2 * v, tl, tm, l, min(r, tm), add_val);
- update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add_val);
- tree[v] = max(tree[2 * v], tree[2 * v + 1]);
- }
- }
- long long query(int v, int tl, int tr, int l, int r) {
- if (l > r)
- return LLONG_MIN;
- if (tl == l && tr == r) {
- return tree[v];
- }
- push(v);
- int tm = (tl + tr) / 2;
- return max(query(2 * v, tl, tm, l, min(r, tm)),
- query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
- }
- void range_add(int l, int r, long long val) {
- update(1, 0, n - 1, l, r, val);
- }
- long long query(int l, int r) {
- return query(1, 0, n - 1, l, r);
- }
- };
- long long HBD_Pious(int N, int K, vector<int> Gifts) {
- vector<vector<long long>> dp(K + 1, vector<long long>(N + 1, 0));
- vector<int> freq(N + 1, 0);
- int distinct = 0;
- for (int i = 0; i < N; ++i) {
- if (freq[Gifts[i]] == 0) {
- distinct++;
- }
- freq[Gifts[i]]++;
- dp[1][i + 1] = distinct;
- }
- if (K == 1) {
- return dp[1][N];
- }
- for (int k_val = 2; k_val <= K; ++k_val) {
- vector<int> last_occurrence(N + 1, -1);
- SegmentTree st(N);
- for (int i = 0; i < N; ++i) {
- if (i < k_val - 1) {
- last_occurrence[Gifts[i]] = i;
- continue;
- }
- int x = Gifts[i];
- int p = last_occurrence[x];
- st.range_add(i, i, dp[k_val - 1][i] + 1);
- int L = (p == -1) ? k_val - 1 : max(p + 1, k_val - 1);
- int R = i - 1;
- if (L <= R) {
- st.range_add(L, R, 1);
- }
- last_occurrence[x] = i;
- dp[k_val][i + 1] = st.query(k_val - 1, i);
- }
- }
- return dp[K][N];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
