In this HackerEarth Levels of a tree problem solution, You are given a tree that consists of n vertex. In this tree, vertex 1 is the root vertex. Here, leveli is defined as a set of vertex where the distance of the vertexes from the root vertex is equal to i. 

You are required to remove at most k levels of the tree in such a manner that after removing the vertexes, the maximum size of the recently-created components is minimum.


HackerEarth Levels of a tree problem solution


HackerEarth Levels of a tree problem solution.

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 400005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
ll res = 1;
x %= mod;
while (n) {
if (n & 1)
res = (res * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}

struct data {
// Use required attributes
int sum, left, right;
int len;
// Default Values
data() : sum(0), left(0), right(0), len(1){};
};

struct SegTree {
int N;
vector<data> st;
vector<bool> cLazy;
vector<int> lazy;

void init(int n) {
N = n;
st.resize(4 * N + 5);
cLazy.assign(4 * N + 5, false);
lazy.assign(4 * N + 5, 0);
}

// Write reqd merge functions
void merge(data &cur, data &l, data &r) {
cur.sum = max(l.sum, r.sum);
cur.sum = max(cur.sum, l.right + r.left);

cur.left = max(l.left, ((l.sum == l.len) ? (l.sum + r.left) : 0ll));
cur.right = max(r.right, ((r.sum == r.len) ? (r.sum + l.right) : 0ll));
cur.len = l.len + r.len;
}

// Handle lazy propagation appriopriately
void propagate(int node, int L, int R) {
if (L != R) {
cLazy[node * 2] = 1;
cLazy[node * 2 + 1] = 1;
lazy[node * 2] = lazy[node];
lazy[node * 2 + 1] = lazy[node];
}
st[node].sum = st[node].left = st[node].right = lazy[node];

cLazy[node] = 0;
lazy[node] = 0;
}

void build(int node, int L, int R) {
if (L == R) {
// st[node].mn = 1e9;
return;
}
int M = (L + R) / 2;
build(node * 2, L, M);
build(node * 2 + 1, M + 1, R);
merge(st[node], st[node * 2], st[node * 2 + 1]);
}

data Query(int node, int L, int R, int i, int j) {
if (cLazy[node])
propagate(node, L, R);
if (j < L || i > R)
return data();
if (i <= L && R <= j)
return st[node];
int M = (L + R) / 2;
data left = Query(node * 2, L, M, i, j);
data right = Query(node * 2 + 1, M + 1, R, i, j);
data cur;
merge(cur, left, right);
return cur;
}

data pQuery(int node, int L, int R, int pos) {
if (cLazy[node])
propagate(node, L, R);
if (L == R)
return st[node];
int M = (L + R) / 2;
if (pos <= M)
return pQuery(node * 2, L, M, pos);
else
return pQuery(node * 2 + 1, M + 1, R, pos);
}

void Update(int node, int L, int R, int i, int j, int val) {
if (cLazy[node])
propagate(node, L, R);
if (j < L || i > R)
return;
if (i <= L && R <= j) {
cLazy[node] = 1;
lazy[node] = val;
propagate(node, L, R);
return;
}
int M = (L + R) / 2;
Update(node * 2, L, M, i, j, val);
Update(node * 2 + 1, M + 1, R, i, j, val);
merge(st[node], st[node * 2], st[node * 2 + 1]);
}

void pUpdate(int node, int L, int R, int pos, int val) {
if (cLazy[node])
propagate(node, L, R);
if (L == R) {
cLazy[node] = 1;
lazy[node] = val;
propagate(node, L, R);
return;
}
int M = (L + R) / 2;
if (pos <= M)
pUpdate(node * 2, L, M, pos, val);
else
pUpdate(node * 2 + 1, M + 1, R, pos, val);
merge(st[node], st[node * 2], st[node * 2 + 1]);
}

data query(int pos) { return pQuery(1, 1, N, pos); }

data query(int l, int r) {
if (l > r)
return data();
return Query(1, 1, N, l, r);
}

void update(int pos, int val) { pUpdate(1, 1, N, pos, val); }

void update(int l, int r, int val) { Update(1, 1, N, l, r, val); }
};

struct Query {
ll L, R;
ll D;
ll indx;
Query() {}
Query(ll L, ll R, ll D, ll indx) : L(L), R(R), D(D), indx(indx) {}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll n, q;
cin >> n >> q;

ll A[n + 5];

for (int i = 1; i <= n; i++) {
cin >> A[i];
}

ll diff[n + 5];

ll offset = 200000;

vector<ll> indicesList[400005];

for (ll i = 1; i < n; i++) {
diff[i] = A[i + 1] - A[i];
indicesList[offset + diff[i]].push_back(i);
}

vector<Query> queryEvent[400005];

for (ll i = 1; i <= q; i++) {
ll L, R, D;
cin >> L >> R >> D;

queryEvent[D + offset].push_back(Query(L, R, D, i));
}

ll ans[q + 5];

SegTree obj;
obj.init(n - 1);

for (ll i = 0; i <= 400000; i++) {
for (int indx : indicesList[i]) {
obj.update(indx, 1);
}
for (Query &query : queryEvent[i]) {
int indx = query.indx;
ans[indx] = obj.query(query.L, query.R - 1).sum + 1;
}
for (int indx : indicesList[i]) {
obj.update(indx, 0);
}
}

for (int i = 1; i <= q; i++)
cout << ans[i] << en;

return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 400005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
ll res = 1;
x %= mod;
while (n) {
if (n & 1)
res = (res * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}

struct data {
// Use required attributes
int sum, left, right;
int len;
// Default Values
data() : sum(0), left(0), right(0), len(1){};
};

struct SegTree {
int N;
vector<data> st;
vector<bool> cLazy;
vector<int> lazy;

void init(int n) {
N = n;
st.resize(4 * N + 5);
cLazy.assign(4 * N + 5, false);
lazy.assign(4 * N + 5, 0);
}

// Write reqd merge functions
void merge(data &cur, data &l, data &r) {
cur.sum = max(l.sum, r.sum);
cur.sum = max(cur.sum, l.right + r.left);

cur.left = max(l.left, ((l.sum == l.len) ? (l.sum + r.left) : 0ll));
cur.right = max(r.right, ((r.sum == r.len) ? (r.sum + l.right) : 0ll));
cur.len = l.len + r.len;
}

// Handle lazy propagation appriopriately
void propagate(int node, int L, int R) {
if (L != R) {
cLazy[node * 2] = 1;
cLazy[node * 2 + 1] = 1;
lazy[node * 2] = lazy[node];
lazy[node * 2 + 1] = lazy[node];
}
st[node].sum = st[node].left = st[node].right = lazy[node];

cLazy[node] = 0;
lazy[node] = 0;
}

void build(int node, int L, int R) {
if (L == R) {
// st[node].mn = 1e9;
return;
}
int M = (L + R) / 2;
build(node * 2, L, M);
build(node * 2 + 1, M + 1, R);
merge(st[node], st[node * 2], st[node * 2 + 1]);
}

data Query(int node, int L, int R, int i, int j) {
if (cLazy[node])
propagate(node, L, R);
if (j < L || i > R)
return data();
if (i <= L && R <= j)
return st[node];
int M = (L + R) / 2;
data left = Query(node * 2, L, M, i, j);
data right = Query(node * 2 + 1, M + 1, R, i, j);
data cur;
merge(cur, left, right);
return cur;
}

data pQuery(int node, int L, int R, int pos) {
if (cLazy[node])
propagate(node, L, R);
if (L == R)
return st[node];
int M = (L + R) / 2;
if (pos <= M)
return pQuery(node * 2, L, M, pos);
else
return pQuery(node * 2 + 1, M + 1, R, pos);
}

void Update(int node, int L, int R, int i, int j, int val) {
if (cLazy[node])
propagate(node, L, R);
if (j < L || i > R)
return;
if (i <= L && R <= j) {
cLazy[node] = 1;
lazy[node] = val;
propagate(node, L, R);
return;
}
int M = (L + R) / 2;
Update(node * 2, L, M, i, j, val);
Update(node * 2 + 1, M + 1, R, i, j, val);
merge(st[node], st[node * 2], st[node * 2 + 1]);
}

void pUpdate(int node, int L, int R, int pos, int val) {
if (cLazy[node])
propagate(node, L, R);
if (L == R) {
cLazy[node] = 1;
lazy[node] = val;
propagate(node, L, R);
return;
}
int M = (L + R) / 2;
if (pos <= M)
pUpdate(node * 2, L, M, pos, val);
else
pUpdate(node * 2 + 1, M + 1, R, pos, val);
merge(st[node], st[node * 2], st[node * 2 + 1]);
}

data query(int pos) { return pQuery(1, 1, N, pos); }

data query(int l, int r) {
if (l > r)
return data();
return Query(1, 1, N, l, r);
}

void update(int pos, int val) { pUpdate(1, 1, N, pos, val); }

void update(int l, int r, int val) { Update(1, 1, N, l, r, val); }
};

struct Query {
ll L, R;
ll D;
ll indx;
Query() {}
Query(ll L, ll R, ll D, ll indx) : L(L), R(R), D(D), indx(indx) {}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll n, q;
cin >> n >> q;

ll A[n + 5];

for (int i = 1; i <= n; i++) {
cin >> A[i];
}

ll diff[n + 5];

ll offset = 200000;

vector<ll> indicesList[400005];

for (ll i = 1; i < n; i++) {
diff[i] = A[i + 1] - A[i];
indicesList[offset + diff[i]].push_back(i);
}

vector<Query> queryEvent[400005];

for (ll i = 1; i <= q; i++) {
ll L, R, D;
cin >> L >> R >> D;

queryEvent[D + offset].push_back(Query(L, R, D, i));
}

ll ans[q + 5];

SegTree obj;
obj.init(n - 1);

for (ll i = 0; i <= 400000; i++) {
for (int indx : indicesList[i]) {
obj.update(indx, 1);
}
for (Query &query : queryEvent[i]) {
int indx = query.indx;
ans[indx] = obj.query(query.L, query.R - 1).sum + 1;
}
for (int indx : indicesList[i]) {
obj.update(indx, 0);
}
}

for (int i = 1; i <= q; i++)
cout << ans[i] << en;

return 0;
}