Auto comment: topic has been updated by oleh1421 (previous revision, new revision, compare).

Auto comment: topic has been updated by oleh1421 (previous revision, new revision, compare).

Contest will start in 2 hours

19.5 hours left till the end of a contest. Don't miss the timer

Thank you for the problems! Here are some of my solutions:

F — a functional graph is a forest with a loop connecting the roots, so we can uniquely determine the number of a node $$$u$$$ not on the loop as the MEX of the numbers for all nodes $$$v$$$ it connects to. In turn, this means that we can determine the only two possible values for the values on the loop: the MEX, and the second MEX in case the first MEX was taken by the node it points to. After we get this, we can fix the value of some point in the loop and do a DP to see if such an assignment is consistent.

G — let $$$dp[i]$$$ be the answer for the prefix $$$[1,i]$$$ if we only use operations within $$$[1,i]$$$. Then, we have $$$dp[i-1]+(1-a[i])\to dp[i]$$$ if we don't do anything; and for all positions $$$j$$$ such that it is possible to cover $$$[j,i]$$$ all with ones and $$$[1,j-1]$$$ without restrictions, we have $$$dp[j-1]+(0[i]-0[j-1])\to dp[i]$$$ where $$$0[i]$$$ is the number of zeroes within $$$a[1,i]$$$. It is reasonable to instead consider $$$dp'[i]=dp[i]-0[i]$$$, giving $$$dp'[j-1]\to dp'[i]$$$.

For each operation $$$[l,r]$$$ let's find the minimum possible $$$dp'[j-1]$$$ over all possible $$$j$$$, if we must use the operation $$$[l,r]$$$. Then the immediate candidate is $$$j=l$$$; we also have candidates given by the intervals $$$[x,y]$$$ where $$$x\le l\le y\le r$$$. If we keep track of the best $$$dp'[j-1]$$$ for all intervals, we can sweep line by $$$r$$$, and the problem becomes to set $$$a[i]\leftarrow \min(a[i],v)$$$ for an interval and to query $$$a[j]$$$, which can be done with a segment tree.