**CBFEAST**

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
```

3.