First of all, this technique isn't anything new, it's a fairly known one, but I couldn't find any resources on this topic other than this comment which is somewhat hard to find, so I decided to write a full blog.

With that being said, let's begin with the blog.

The problem

Lets consider the following problem: A graph is given with $$$N$$$ nodes and $$$Q$$$ queries. Each query is one of the following:

• Add edge $$$(u,v)$$$
• Remove edge $$$(u,v)$$$
• Query the number of connected components in the graph

The timeline

Lets imagine a timeline, from time $$$1$$$ to time $$$Q$$$, at each moment either some edge gets added, removed, or a query gets asked.

Now the main idea of this technique is instead of dealing with deletions, for each edge we determine some intervals during which it exists. Namely if edge $$$(u, v)$$$ gets added at time $$$A$$$ and then later removed at time $$$B$$$ then that edge will obviously exist in the time frame $$$[A, B)$$$.

The Segment Tree on time

Now we've turned the problem into a range update problem, which suggests using a segment tree. We build a segment tree over the timeline. For each node, we store a list of edges that are active throughout the segment represented by that node.

Each interval gets decomposed into $$$O( \log Q)$$$ segments in the tree, and for each of those segments, we simply add the corresponding edge to the node.

After building the tree, we will run a DFS on it while maintaining a DSU with rollbacks (this is a well-known structure that can handle operations in $$$O(\log N)$$$).

At each node, we add all the edges in the node to the DSU, recurse downwards, and then rollback.

At the leaves, if the time corresponds to a query we can easily answer it since our DSU is already built.

This way we will handle everything offline in $$$O(Q \log Q \log N)$$$.

How is this useful?

You may be wondering by this point how this is useful at all since Dynamic Connectivity can be solved both online and offline in a better time complexity.It turns out this technique can be generalized.

Notice that the only part specific to the problem that we used in our solution is the Rollback DSU. So this technique can be applied in any problem with addition and deletion of pretty much anything to any structure. The only condition is that we need to be able to handle addition, and most importantly, rollbacks in a good time complexity.

In return for writing this amazing blog I am asking you to link any problems that can be solved with this technique in the comments.

Big thanks to EntityPlantt for using his grammar police abilities for once to not ragebait me and instead help me fix my terrible grammar.

I want to brag a little (again)

So I kinda cooked this year and got a gold medal, I was 5th overall scoring 446.5 points.

Huge orz to ArturSmolenski for winning the thing.

Big thanks to:

• MODDI and Mystic03 for amazing team leading

• NemanjaSo2005 for giving me Nemanja energy

• gkos for giving me Kos energy

• bornag for having a very inspirational comeback on day 2 after his very innovative ideas on day 1

So, hours have passed since the ratings have been update for the div 2 participants, when will the ratings be updated for the div 1 participants of last round (Codeforces Round 1028 (Div. 1))

Gellyfish MagicalFlower errorgorn MikeMirzayanov

(Wrong answers only)

Huge orz to damjandavkov for becoming Macedonia's first GM on codeforces. Wtf Strong!

So I want to brag a little

I got bronze medal this year, 19 points away from silver, hope I get silver next year :D

orz to EntityPlantt and mkkkkkkkk for getting bronze too, also to biserailieva for moral support

Also thanks to Bidik and MODDI for amazing team leading :D

So yesterday I sent a code of this search in a group chat as a joke but surprisingly everyone praised it and iframe_ dubbed it as "Fenwick search" and now I am farming contribution making a blog about it.

Fenwick Search

Lets say you want to search on the interval $$$[1, n)$$$ and lets say you want to find the minimal position that satisfy a certain property. Also let the minimal position that satisfies said property be $$$ans$$$

So, in regular binary search you keep a left bound and a right bound and you change them accordingly, but in Fenwick search you only keep track of the middle bound. Firstly initialize the middle bound as the highest power of 2 that is less than n.

The gist of Fenwick search is transforming the middle bound into $$$ans$$$, we do that by manipulating the bits in the middle bound. Specifically for every set bit in $$$ans$$$ we set the bit after the last set bit in the middle bound and we shift it left until it matches the desired bit in $$$ans$$$. For example, lets say we start with middle bound $$$16$$$ and we want to transform it into $$$ans = 22$$$, $$$16_{10} = 10000_2 \rightarrow 11000_2 \rightarrow 10100_2 \rightarrow 10110_2 = 22_{10} $$$

But how do we actually transform it? Well its simple, we check if the middle bound satisfies the property if so, you shift the last set bit one to the left, if it does not satisfy you need to set a new bit after the last set. You need to perform this checking and updating exactly $$$\lfloor{log2(n - 1)}\rfloor$$$. There is a single edge case, if the middle bound is $$$\ge n$$$ you always need to shift the last bit to the right.

To set a new bit after the last set you need to update the middle bound like this: $$$m = m + (m \ \text{&} \ (-m)) \gt \gt 1$$$ and to shift the last bit to the right you need to update the middle bound like this:$$$m = m - (m \ \text{&} \ (-m)) \gt \gt 1$$$

int tm = 1<<(LOG);
int ans = -1;
for(int i = 0;i < LOG;i++){
    if(tm >= n)tm -= (tm & -tm) >> 1;
    else if(check(tm)){
        ans = tm;
        tm -= (tm & -tm) >> 1;
    }else tm += (tm & -tm) >> 1;
}

This is the code, $$$check(x)$$$ is function that checks the property the we are searching

That's it, sorry for my bad english I tried to make it as good as possible