First of all notice that constant K which is given (which could differ for each query, if task were different).
Now every update maps to 2K length segment from which we could query -> segment trees.
Now you are updating interval [c-K, c+K] with d, and update means add this to front (you can do operations 1 and 2 separately so they are both adding to front). Query is done for single element c while descending the tree.
This is now done similar to segment trees Assingment on segment.
Also, similar to Dynamic max subarray question, you are keeping maximal subarray, prefix, suffix and sum in each node of implicit “lazy-prop” segtree. Complexity O(QlogK)
If you are able to understand beforementioned similar problems, and implicit segment trees my
[2] should be self-explanatory. Also, notice if $K$ was not constant for each query, range we would be updating might not be contiguous and linear, i.e. i don't know if it would be solvable in $QlogX$ complexity.
**EDGEDIR**
Only works if number of edges is even.
Cut out a random tree with DFS and assign all other edges randomly. Now every node of a tree will be associated with even or odd indegree from currently assigned edges. Now assign the edges of a tree bottom-up from node to his parent (not in that direction but in a way that makes child node even degree). Only the root will be indeterminete degree, but it will have to have even degree since total number of edges is even, and all other nodes have even degree by construction. Here is the
Thanks, so for for example -> ppss|sssppp <-, where you are pushing to p(prefix), and one possible solution is obviously sum of max suffixes left and right then.
I don’t understand what do you mean by assigning the edges bottom up. I saw a large number of submissions using the same technique but could not understand the “updating edges up to the root” part. (I understand the spanning tree part though)
If we do this:
For every leaf, travel up to the root of the tree assigning the edges correctly, then it will work correctly but will time out.
I am not able to understand how a single DFS (I mean after finding the spanning tree) can accomplish this update. Any help will be highly appreciated. Thanks.
The theory behind solving EDGEDIR is fairly simple:
Create a spanning tree.
DFS to determine the distance of each node from root.
Direct any edges that are not part of the spanning tree however you like.
Now every node at distance d from root has an undirected edge connecting it to a node at distance d-1, and we can always direct that edge in a way that leaves the node at distance d with an even number of indegrees. If we sort the edges and do this with the most distant edges first, the only node that we can’t control is root.
Root will only be wrong if there is an odd number of edges, in which case the problem is unsolvable.
@upintheair. Consider a directed graph with odd number of edges. Every edge has a tail(source vertex) and a head(destination vertex). Thus, each edge contributes one to the indegree of some vertex and one to the outdegree of some vertex, which implies number of edges are equal to the sum of indegrees of all vertices. If every vertex has to have even indegree then the total indegree of all vertices would also be even. But this wouldn’t be possible if there are odd edges(because then sum of indegree of vertices would be odd.)
