PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author & Editorialist: Cisco Ortega
Tester : Encho Mishinev
DIFFICULTY:
Medium
PREREQUISITES:
Data Structures on Trees, Stack, Greedy
PROBLEM:
A “mountain range” can be modeled by a polyline in a 2D plane that passes through N points p_1 = (1,h_1), p_2 = (2, h_2), \ldots, p_N = (N, h_N), in this order, where h_i is a positive integer for each valid i. This polyline divides the set of points \{(x, z): 1 \le x \le N\} into two regions. The “solid” part of the mountain range is the “bottom” region, i.e. the region that contains the x-axis.
Each point p_i is initially assigned the value a_i. Chef can glide from point to point, and the total value of a journey is just the sum of the values of all points visited. However, there are some restrictions,
- Chef can only glide from a higher den to a strictly lower den, i.e. if he glides from a den at p_i to a den at p_j, then h_i \gt h_j must hold.
- Chef can only glide in one direction and never look back, i.e. if he starts travelling in the direction of decreasing x, he must keep travelling in that direction until the end of the journey, and if he starts travelling in the direction of increasing x, he must keep travelling in that direction until the end of the journey too.
- Chef cannot travel through solid mountain, i.e. he can only glide from a den at p_i to a den at p_j if the line segment connecting the points p_i and p_j does not intersect the “solid” part of the mountain range. However, it may touch the border of the mountain range, i.e. the polyline itself.
You must process Q queries. There are two types of queries:
-
1 b k: The value of point p_b should be changed to k instead for all future queries. -
2 b c: Find the maximum possible value of all journeys that start at p_b and end at p_c
QUICK EXPLANATION:
Suppose that b \leq c.
- It is always optimal to visit as many points as possible on the journey.
- Suppose we want to plan a journey from p_b \to \dots \to p_c. Let i be the greatest integer less than c such that h_i > h_c, i.e. p_i is the point nearest p_c to its left that is higher up than it. Then, it is always optimal to visit p_i, i.e. the journey goes p_b \to \dots \to p_i \to p_c. Call i the “optimal previous” of c.
- For the journey p_b \to \dots \to p_c, we should start at c, then visit its optimal previous, then visit its optimal previous, and so on, until we arrive at b.
- For each 1 \leq c \leq N, connect c with its optimal previous. This creates a rooted forest.
- If b is not an ancestor of c, then the journey is impossible. Otherwise, the answer is the sum of the a_i of all nodes on the path from c to b.
- Point updates and path sum queries can be handled by flattening the tree, rudimentary heavy-light decomposition, etc.
For when b > c, create another rooted forest that represents motion in the other direction.
EXPLANATION:
To simplify things, let’s assume that b \leq c for all queries of the second type. So, Chef is always traveling with increasing x-coordinates.
Since all values are positive, a journey from b to c can always be improved if we can squeeze in another point to be visited. So, let’s try to determine a point that we for sure will visit on the way from p_b\to \dots \to p_c.
Let i be the greatest integer less than c such that i < c and h_i > h_c, i.e. p_i is the point nearest p_c to its left that is higher up than it. Call i the “optimal previous” of c. Since no other point between i and c is higher than h_c, we know it is always possible to travel from p_i to p_c.
We call i the optimal previous because we can show that it is always optimal to include p_i in Chef’s journey. Consider any optimal journey from p_b to p_c that does not include p_i. We can then improve the score of that journey by first passing through p_i and then ending on p_c.
This reduces the problem then to finding the maximum possible value of all journeys that start at p_b and end at p_i. But then, by the same argument, we know we have to pass through the optimal previous of i, and so on.
So, we now can build the journey with the following algorithm. Start at c, then visit its optimal previous, then visit its optimal previous, and so on, until we end up at b. If we don’t end up at b, then the journey is impossible.
Each point has a unique optimal previous, if it has one at all. Determining the optimal previous of all points can be done in \mathcal{O}(N) using a stack.
If we connect each point to its optimal previous, we end up defining a rooted tree (or rather, a forest). Checking if it is possible to get from p_b to p_c is a matter of checking if b is an ancestor of c in its tree. Then, the value of the maximum possible journey is simply the sum of the values of all nodes on the path from b to c.
What about when b > c? Simple—just create two different forests, one for left-to-right motion, and one for right-to-left motion. Maintain updates on both, and use the appropriate one when querying.
Handling point updates and path sum queries can easily be maintained using your favorite tree data structure—you could flatten the tree, or use Heavy Light, or whatever you want.
The runtime is thus \mathcal{O}(\log n) (with Tree Flattening) or \mathcal{O}(\log^2 N) (with Heavy-Light Decomposition) per query. We are okay with letting \mathcal{O}(\log^2 N) solutions pass if they are optimized (both the setter’s Heavy-Light and Tree Flattening solution finish in 0.20s).
I will briefly discuss one method for solving this, which is by flattening the tree, since it is the simpler one of the two.
For our problem, we may get a forest, so create a dummy node 0 that is root of all our trees.
Now, we perform a DFS tree traversal starting from the root. We maintain a global timer which starts at 0, and maintain two arrays entr and ext, corresponding to the entry and exit time of each node.
- When you enter a node
u, recordentr[u]=timer;then incrementtimer += 1; - When you exit a node
u, recordext[u]=timerthen incrementtimer += 1;
Our tree has n+1 vertices, so each of the integers from 0 to 2n+1 is associated with a particular node, on either entry or exit. You can imagine tracing the tree traversal with a continuous line, then unwrapping and flattening it out (seriously, draw a picture, it will help).
Now, note that the entr and ext of all nodes in the subtree of some u must appear between entr[u] and ext[u], which can be more easily visualized if you have a picture of the traced path.
How can we check if b is an ancestor of c? That’s equivalent to c being a descendant of b, i.e. c exists in the subtree of b. So, we just check if entr[b] <= entr[c] and ext[c] <= ext[b] (actually it doesn’t matter if we use entr[c] or ext[c] for each check).
How about the path queries? We create an array flat, then set flat[entr[u]] = a[u] and flat[ext[u]] = -a[u]. If b is an ancestor c, then the sum of all nodes on the path from b to c is just the sum of flat[entr[b]] until flat[entr[c]]. Why?
This range contains all the nodes that we visit before c. If it is on the path directly between b and c, then only its entr is in the range and not its ext, because we only exit each of those nodes after we are done with all its descendants (and c is one of them). However, if a node is not on that path, we must have entered and then exited it before arriving at c. That means both its entr and exit are in the given range, and they will cancel each other out when summed.
Here is another way to visualize this. Consider the stack of recursive calls for our DFS. When you enter a node u, push u onto the stack. When you exit a node u, pop u from the stack. When you reach c, the only nodes on the stack are those on the path from b to c.
Now, instead instead of pushing u onto stack, push a[u]. And, instead of popping u from the stack, push -a[u]. Then, we see that the sum of the values of the nodes on the path from b to c is equal to the sum of some consecutive range of “recursive calls”. This range is what entr[b] and entr[c] keeps track of.
When doing a point update on u, make sure to update both flat[entr[u]] and flat[ext[u]].
We can maintain point updates and range sum queries with either a segment tree or a Fenwick tree, giving \mathcal{O}(\log n) time per query.
Question: Suppose you should start at b but you can choose whatever ending point c that you want. How can answer those queries quickly?
Question: What do you do for path queries from u to v where one is not the ancestor of another?
Question: Why does this trick not work with range max or range min queries?
SOLUTIONS:
Setter's Tree Flattening Solution
#include <iostream>
#include <stack>
#include <vector>
#define M (L+R)/2
using namespace std;
typedef long long LL;
struct SegmentTree //0-indexed point add update, range sum query
{
int n;
vector<LL> a;
void pull(int node){ a[node] = a[node<<1]+a[(node<<1)+1]; }
void build(vector<LL>& arr, int L, int R, int node)
{
if(L==R)
{
a[node] = arr[L];
return;
}
build(arr,L,M,node<<1);
build(arr,M+1,R,(node<<1)+1);
pull(node);
}
void update(int L, int R, int pt, LL val, int node)
{
if(L==R)
{
a[node] = val;
return;
}
if(pt <= M)
update(L,M,pt,val,node<<1);
else
update(M+1,R,pt,val,(node<<1)+1);
pull(node);
}
void update(int pt, LL val){ update(0,n-1,pt,val,1); }
LL query(int L, int R, int left, int right, int node)
{
if(L > R || R < left || L > right)
return 0;
if(left <= L && R <= right)
return a[node];
else
return query(L,M,left,right,node<<1)+query(M+1,R,left,right,(node<<1)+1);
}
LL query(int left, int right){ return query(0,n-1,left,right,1); }
SegmentTree(vector<LL>& arr)
{
n = arr.size();
a = vector<LL>(4*(arr.size()+1));
build(arr,0,n-1,1);
}
SegmentTree(){}
};
struct FlattenedTree
{
int root, n;
vector<vector<int> > adj;
vector<int> entr, ext;
int timer = 0;
void dfs(int u, int prev)
{
entr[u] = timer++;
for(const int& v : adj[u])
if(v != prev)
dfs(v,u);
ext[u] = timer++;
}
SegmentTree segmentTree;
FlattenedTree(vector<int>& p, vector<int>& s)
{
n = p.size();
adj = vector<vector<int>>(n);
for(int u = 0; u < n; u++)
if(p[u]!=-1)
{
adj[u].push_back(p[u]);
adj[p[u]].push_back(u);
}
else
root = u;
entr = vector<int>(n);
ext = vector<int>(n);
dfs(root, -1);
vector<LL> flattenedTree(2*n);
for(int u = 0; u < n; u++)
{
flattenedTree[entr[u]] = s[u];
flattenedTree[ext[u]] = -s[u];
}
segmentTree = SegmentTree(flattenedTree);
}
void update(int pt, LL val)
{
segmentTree.update(entr[pt],val);
segmentTree.update(ext[pt],-val);
}
bool is_ancestor(int u, int v) //is u an ancestor of v ?
{
return entr[u] <= entr[v] && ext[v] <= ext[u];
}
LL query(int u, int v)
{
if(!is_ancestor(u,v))
return -1;
else
return segmentTree.query(entr[u],entr[v]);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q; cin >> n >> q;
vector<int> h(n+1,0), s(n+1,0);
//0 is a dummy point, to be the "root" of the tree
for(int i = 1; i <= n; i++)
cin >> h[i];
for(int i = 1; i <= n; i++)
cin >> s[i];
stack<int> travelToRight, travelToLeft;
vector<int> pRight(n+1), pLeft(n+1);
pRight[0] = pLeft[0] = -1;
auto iterate = [](int i, stack<int>& traveled, vector<int>& p, vector<int>& h)
{
while(!traveled.empty() && !(h[traveled.top()] > h[i]))
traveled.pop();
if(traveled.empty())
p[i] = 0;
else
p[i] = traveled.top();
traveled.push(i);
};
for(int i = 1; i <= n; i++)
iterate(i,travelToRight,pRight,h);
for(int i = n; i >= 1; i--)
iterate(i,travelToLeft,pLeft,h);
FlattenedTree flat_right(pRight,s), flat_left(pLeft,s);
while(q--)
{
int t, u, v; cin >> t >> u >> v;
if(t==1)
{
flat_right.update(u,v);
flat_left.update(u,v);
}
else
{
if(u <= v)
cout<<flat_right.query(u,v)<<'\n';
else
cout<<flat_left.query(u,v)<<'\n';
}
}
cout<<flush;
}
Setter's Heavy-Light Solution
#include <iostream>
#include <stack>
#include <vector>
#define M (L+R)/2
using namespace std;
typedef long long LL;
struct SegmentTree //0-indexed point add update, range sum query
{
int n;
vector<LL> a;
void pull(int node){ a[node] = a[node<<1]+a[(node<<1)+1]; }
void build(vector<LL>& arr, int L, int R, int node)
{
if(L==R)
{
a[node] = arr[L];
return;
}
build(arr,L,M,node<<1);
build(arr,M+1,R,(node<<1)+1);
pull(node);
}
void update(int L, int R, int pt, LL val, int node)
{
if(L==R)
{
a[node] = val;
return;
}
if(pt <= M)
update(L,M,pt,val,node<<1);
else
update(M+1,R,pt,val,(node<<1)+1);
pull(node);
}
void update(int pt, LL val){ update(0,n-1,pt,val,1); }
LL query(int L, int R, int left, int right, int node)
{
if(L > R || R < left || L > right)
return 0;
if(left <= L && R <= right)
return a[node];
else
return query(L,M,left,right,node<<1)+query(M+1,R,left,right,(node<<1)+1);
}
LL query(int left, int right){ return query(0,n-1,left,right,1); }
SegmentTree(vector<LL>& arr)
{
n = arr.size();
a = vector<LL>(4*(arr.size()+1));
build(arr,0,n-1,1);
}
SegmentTree(){}
};
struct HeavyLight
{
int root, n;
vector<vector<int> > adj;
vector<int> p, size, depth, disc, head;
void dfs_heavy(int u, int p, int d=0)
{
size[u] = 1;
depth[u] = d;
int heavy_child = -1;
for(int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i];
if(v != p)
{
dfs_heavy(v,u,d+1);
size[u] += size[v];
if(heavy_child==-1 || size[v] >= size[adj[u][heavy_child]])
heavy_child = i;
}
}
if(heavy_child != -1)
swap(adj[u][0],adj[u][heavy_child]);
}
int timer = 0;
void dfs_disc(int u, int p)
{
if(u==root) head[u] = u;
disc[u] = timer++;
for(int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i];
if(v != p)
{
if(i==0)
head[v] = head[u];
else
head[v] = v;
dfs_disc(v,u);
}
}
}
bool is_ancestor(int u, int v) //is u an ancestor of v ?
{
if(u==root) return true;
if(u==v) return true;
if(depth[v] <= depth[u]) return false;
while(depth[u] < depth[head[v]])
v = p[head[v]];
return head[u]==head[v];
}
SegmentTree segmentTree;
HeavyLight(vector<int>& p, vector<int>& s)
{
n = p.size();
this->p = vector<int>(n);
copy(p.begin(),p.end(),(this->p).begin());
adj = vector<vector<int> >(n);
for(int u = 0; u < n; u++)
if(p[u]!=-1)
{
adj[u].push_back(p[u]);
adj[p[u]].push_back(u);
}
else
root = u;
size = vector<int>(n);
depth = vector<int>(n);
disc = vector<int>(n);
head = vector<int>(n);
dfs_heavy(root, -1);
dfs_disc(root,-1);
vector<LL> flattenedTree(n);
for(int i = 0; i < n; i++)
flattenedTree[disc[i]] = s[i];
segmentTree = SegmentTree(flattenedTree);
}
void update(int pt, LL val)
{
segmentTree.update(disc[pt],val);
}
LL query(int u, int v)
{
if(!is_ancestor(u,v))
return -1;
LL ans = 0;
while(head[v] != head[u])
{
ans += segmentTree.query(disc[head[v]],disc[v]);
v = p[head[v]];
}
ans += segmentTree.query(disc[u],disc[v]);
return ans;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q; cin >> n >> q;
vector<int> h(n+1,0), s(n+1,0);
//0 is a dummy point, to be the "root" of the tree
for(int i = 1; i <= n; i++)
cin >> h[i];
for(int i = 1; i <= n; i++)
cin >> s[i];
stack<int> travelToRight, travelToLeft;
vector<int> pRight(n+1), pLeft(n+1);
pRight[0] = pLeft[0] = -1;
auto iterate = [](int i, stack<int>& traveled, vector<int>& p, vector<int>& h)
{
while(!traveled.empty() && !(h[traveled.top()] > h[i]))
traveled.pop();
if(traveled.empty())
p[i] = 0;
else
p[i] = traveled.top();
traveled.push(i);
};
for(int i = 1; i <= n; i++)
iterate(i,travelToRight,pRight,h);
for(int i = n; i >= 1; i--)
iterate(i,travelToLeft,pLeft,h);
HeavyLight HLD_right(pRight,s), HLD_left(pLeft,s);
while(q--)
{
int t, u, v; cin >> t >> u >> v;
if(t==1)
{
HLD_right.update(u,v);
HLD_left.update(u,v);
}
else
{
if(u <= v)
cout<<HLD_right.query(u,v)<<'\n';
else
cout<<HLD_left.query(u,v)<<'\n';
}
}
cout<<flush;
}
Tester's Solution
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long llong;
int n,q;
int h[200111];
llong a[200111];
vector<int> st;
vector<int> Tree[2][200111];
bool root[2][200111];
int inCtr[2];
int inVal[2][200111];
int lastIn[2][200111];
int parent[2][200111];
llong IT[2][800111];
int LEAFOFFSET;
bool isChild(int t, int vp, int vc)
{
return inVal[t][vc] >= inVal[t][vp] && inVal[t][vc] <= lastIn[t][vp];
}
void recUpd(int t, int ver, int L, int R, int l, int r, llong val)
{
if (L >= l && R <= r)
{
IT[t][ver] += val;
return;
}
else if (L > r || R < l)
return;
else
{
recUpd(t, 2*ver, L, (L+R)/2, l, r, val);
recUpd(t, 2*ver+1, (L+R)/2+1, R, l, r, val);
}
}
void updVal(int t, int node, llong val)
{
int L = inVal[t][node];
int R = lastIn[t][node];
recUpd(t, 1, 1, LEAFOFFSET+1, L, R, val);
}
llong rootPath(int t, int node)
{
if (node == 0)
return 0LL;
int ind = inVal[t][node] + LEAFOFFSET;
llong ans = 0;
while(ind > 0)
{
ans += IT[t][ind];
ind /= 2;
}
return ans;
}
void flattenTree(int t, int ver)
{
int i;
inCtr[t]++;
inVal[t][ver] = inCtr[t];
for (i=0;i<Tree[t][ver].size();i++)
{
parent[t][ Tree[t][ver][i] ] = ver;
flattenTree(t, Tree[t][ver][i]);
}
lastIn[t][ver] = inCtr[t];
}
int main()
{
int i,j;
scanf("%d %d", &n, &q);
for (i=1;i<=n;i++)
{
scanf("%d", &h[i]);
}
for (i=1;i<=n;i++)
{
scanf("%lld", &a[i]);
}
LEAFOFFSET = 1;
while(LEAFOFFSET < n)
LEAFOFFSET *= 2;
LEAFOFFSET--;
for (i=1;i<=n;i++)
{
while(!st.empty() && h[st.back()] <= h[i])
st.pop_back();
if (!st.empty())
Tree[0][st.back()].push_back(i);
else
root[0][i] = true;
st.push_back(i);
}
st.clear();
for (i=n;i>=1;i--)
{
while(!st.empty() && h[st.back()] <= h[i])
st.pop_back();
if (!st.empty())
Tree[1][st.back()].push_back(i);
else
root[1][i] = true;
st.push_back(i);
}
for (i=1;i<=n;i++)
{
if (root[0][i])
flattenTree(0, i);
if (root[1][i])
flattenTree(1, i);
}
for (i=1;i<=n;i++)
{
updVal(0, i, a[i]);
updVal(1, i, a[i]);
}
for (i=1;i<=q;i++)
{
int cm, v, k;
scanf("%d %d %d", &cm, &v, &k);
if (cm == 1)
{
int change = k - a[v];
updVal(0, v, change);
updVal(1, v, change);
a[v] = k;
}
else
{
int t = 0;
if (v > k)
t = 1;
if (!isChild(t, v, k))
printf("-1\n");
else
printf("%lld\n", rootPath(t, k) - rootPath(t, parent[t][v]));
}
}
}
