A brief talk on irrotational Treap (based on the balanced tree of literature and art of Luogu P3391)

Let's talk about it. It's really shallow. It's completely based on the following inscription ↓

Luogu P3391

Look at the questions myself. I'm too lazy to stick...

analysis

In fact, there is nothing to analyze. This is a template problem of Splay tree, which solves the interval maintenance problem that can not be solved by general Treap.

Because Splay's code is smelly, long and difficult to memorize, we invited the non rotating Treap, which is said to have better time and better mobility.

Irrotational Treap

Split split

Irrotational Treap is a balanced tree type based on splitting. In essence, it is a random number binary heap based on Treap to ensure balance, but its operation is simpler than general Treap, and its function is also more excellent, which can solve some problems that general Treap can't solve.

First, let's talk about the most basic splitting operation of irrotational Treap.

Let's see a simple BST tree:

Let's give a weight val, where we assume 4. Let's cut the tree into two sections, one less than or equal to 4 and the other greater than 4.

So we scan from the root
At this time, we find that the weight of this node is greater than the weight 4 given by us, so we can boldly separate it from its left subtree and connect it to our assumed r node (that is, the right half of our split part. The implementation of the program directly sets the root of R to the node with the weight 5), because this half is obviously greater than 4. (the red edge drawn in the figure does not actually exist, and the point connected is the root of the R tree)

At this time, we enter its left child node query and find that it is less than the weight 4, so we boldly cut the connection between its right node and it, and then "connect" it to l to become the root node of L tree.
At this time, we enter its right node for query, that is, the lonely three. We find that it is still less than the weight 4, so we connect it to the right son of node 2.

Here, we don't encounter the case that the weight is greater than 4 when we query the left subtree. If so, we just need to arrange it on the left subtree of 5 nodes.

Here is a more complex tree:

The code of this part is given below:

	void Update(int rt){
		tr[rt].siz = tr[tr[rt].ls].siz + tr[tr[rt].rs].siz + 1;
	}//This is the Update of a very common tree, which will not be repeated here
	void SplitByVal(int rt, int v, int &l, int &r){
		if(!rt){
			l = r = 0;
			return ;
		}
		if(v >= tr[rt].val){
			l = rt;
			SplitByVal(tr[rt].rs, v, tr[rt].rs, r);
		}else{
			r = rt;
			SplitByVal(tr[rt].ls, v, l, tr[rt].ls);
		}
		Update(rt);
	}

Merge

The merging operation of irrotational tree is to merge the left and right trees into one according to the rand value and the rule of small root heap (I won't stop you if you want to write a large root heap). The specific operation is to find the root node with the smaller rand value in the two trees we have given as the root node. If we take the root of the left tree as the root of the merged tree, we will recursively merge its right subtree with the right tree. If we select the right tree at this time, all operations are the opposite.


(node 5 on the left of the above figure is missing. Please repair it by yourself)

Although the tree in the above figure is not so balanced, as long as our data is random enough, it can still ensure the balance. (since this graph is the rand value I added after breaking up into two, the final structure is different from the original one. In theory, the reconstructed graph should be the same as the original one?)

The key codes are as follows:

	int Merge(int l, int r){
		if(!l || !r) return l | r;
		int rt;
		if(tr[l].dat <= tr[r].dat){
			rt = l;
			tr[rt].rs = Merge(tr[l].rs, r);
		}else{
			rt = r;
			tr[rt].ls = Merge(l, tr[r].ls);
		}
		Update(rt);
		return rt;
	}

Seeing this, the smart one must ask, "Oh, oh, you're just taking it apart and merging it. What's the use!?!?!?"

Hey, don't worry, the mysterious place will be here soon.

Insert

If we want to add a point with a weight of 7 to the above tree, we only need to split the whole tree with a weight of 7, then merge the left tree with the node, and then merge with the right tree.

If you want to turn around, I won't stop you

The key codes are as follows:

	int NewPoint(int v){
		++id;
		tr[id].ls = tr[id].rs = 0;
		tr[id].val = v;
		tr[id].dat = rd();
		tr[id].siz = 1;
		return id;
	}//Open a new space for the node
	void Insert(int &rt, int v){
		int x = 0, y = 0;
		SplitByVal(rt, v, x, y);
		x = Merge(x, NewPoint(v));
		rt = Merge(x, y);
	}

Do you think it's wonderful? Let's take a look at deletion.

Delete Erase

Similarly, we want to delete the node with the weight v on the tree. We just need to divide the tree into left and right according to the weight v (recorded as X and z), and then separate the left tree (x) according to the weight v-1 (recorded as X (covering the original x) and y). At this time, we only need to combine X and Z, so we delete the node with the ownership value v on the tree.

This picture doesn't seem so rigorous. Just make do with it and understand what I mean.

The key codes are as follows:

	void Erase(int &rt, int v){
		int x = 0, y = 0, z = 0;
		SplitByVal(rt, v, x, z);
		SplitByVal(x, v - 1, x, y);
		rt = Merge(x, z); 
	}

But if we only need to delete one of them, we can merge the left and right subtrees of Y and overwrite y, and finally let xyz merge.


The above figure is still very lax. I'll take a look.

The key codes are as follows:

	void Erase(int &rt, int v){
		int x = 0, y = 0, z = 0;
		SplitBySize(rt, v, x, z);
		SplitBySize(x, v - 1, x, y);
		y = Merge(tr[y].ls, tr[y].rs);
		rt = Merge(Merge(x, y), z); 
	}

The above are the four most basic operations. I didn't type other expansion operations. I stuck the code of our dear ljx senior here. If you are interested, you can have a look:

Other operations

The code style of ljx senior is really quite different from mine (mine is really ugly). I haven't seen these three operations in detail. You can make do with them first (mainly the variable naming is quite different).

    int kth(int o,int k)
    {
        while(1)
        {
            int lsiz = tr[tr[o].ls].siz + 1;
            if(lsiz > k) o = tr[o].ls;
            if(lsiz ==k) break;
            if(lsiz < k) o = tr[o].rs, k -= lsiz;
        }
        return tr[o].val;
    }
    int lower_bound(int &o,int v)
    {
        int x = 0, y = 0, tmp;
        split(o, v - 1, x, y);
        tmp = tr[x].siz + 1;
        o = merge(x, y);
        return tmp;
    }
    int upper_bound(int &o,int v)
    {
        int x = 0, y = 0, tmp;
        split(o, v, x, y);
        tmp = tr[x].siz + 1;
        o = merge(x, y);
        return tmp;
    }

Get back to the point

Now let's go back to this problem. This problem only requires us to flip the given sequence and output the final sequence. Therefore, our Erase operation can't be used at all. In fact, in theory, Insert doesn't need to Merge directly, but I still play it in order to get on the board.

But for this problem, we don't need the weight stored on the node, so how do we know where to find the one we need. Obviously, the size of the left subtree of the current node is its position in the original sequence. You can understand this process by simulating it yourself.

Therefore, we can change the Split operation based on the weight value (Val) to the subtree size (Siz), which can be similar to the GetValByRank operation in ordinary tree.

The key codes are as follows:

	void SplitBySize(int rt, int rk, int &l, int &r){
		if(!rt){
			l = r = 0;
			return ;
		}
		if(rk >= tr[tr[rt].ls].siz + 1){
			l = rt;
			SplitBySize(tr[rt].rs, rk - (tr[tr[rt].ls].siz + 1), tr[rt].rs, r);
		}else{
			r = rt;
			SplitBySize(tr[rt].ls, rk, l, tr[rt].ls);
		}
		Update(rt);
	}

So what about the flip operation? We can draw an analogy to the lazy tag in the line segment tree and put a tag on the root node corresponding to the interval we need, which means that the subtree has been flipped, but I haven't adjusted the internal order yet. Until the subsequent operations such as Insert and Merge need to access its subtree, we will mark it down. At this time, we only need to exchange its left and right subtrees and tag its left and right subtrees (or adjust the tag to be more rigorous).

The key codes are as follows:

	void PushDown(int rt){
		if(tr[rt].tag){
			swap(tr[rt].ls, tr[rt].rs);
			if(tr[rt].ls) tr[tr[rt].ls].tag ^= 1;
			if(tr[rt].rs) tr[tr[rt].rs].tag ^= 1;
			tr[rt].tag = 0;
		}
	}
	void Rotate(int l, int r){
		int x, y, z;
		SplitBySize(rt, l - 1, x, y);
		SplitBySize(y, r - l + 1, y, z);
		tr[y].tag ^= 1;
		rt = Merge(Merge(x, y), z); 
	}

In this way, our problem can be solved easily.

Finally, release complete (not) code:

//Header file and fast read omit
struct Point{
	int ls, rs;
	int siz;
	int val, dat;
	int tag;
};
mt19937 rd(60505);
int rt;
struct SplitTreap{//Worship FHQ boss orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz 
	Point tr[MAXN];
	int id;
	void Update(int rt){
		tr[rt].siz = tr[tr[rt].ls].siz + tr[tr[rt].rs].siz + 1;
	}
	void PushDown(int rt){
		if(tr[rt].tag){
			swap(tr[rt].ls, tr[rt].rs);
			if(tr[rt].ls) tr[tr[rt].ls].tag ^= 1;
			if(tr[rt].rs) tr[tr[rt].rs].tag ^= 1;
			tr[rt].tag = 0;
		}
	}
	void SplitBySize(int rt, int rk, int &l, int &r){
		if(!rt){
			l = r = 0;
			return ;
		}
		PushDown(rt);
		if(rk >= tr[tr[rt].ls].siz + 1){
			l = rt;
			SplitBySize(tr[rt].rs, rk - (tr[tr[rt].ls].siz + 1), tr[rt].rs, r);
		}else{
			r = rt;
			SplitBySize(tr[rt].ls, rk, l, tr[rt].ls);
		}
		Update(rt);
	}
	int Merge(int l, int r){
		if(!l || !r) return l | r;
		int rt;
		if(tr[l].dat <= tr[r].dat){
			PushDown(l);
			rt = l;
			tr[rt].rs = Merge(tr[l].rs, r);
		}else{
			PushDown(r);
			rt = r;
			tr[rt].ls = Merge(l, tr[r].ls);
		}
		Update(rt);
		return rt;
	}
	int NewPoint(int v){
		++id;
		tr[id].ls = tr[id].rs = 0;
		tr[id].val = v;
		tr[id].dat = rd();
		tr[id].siz = 1;
		return id;
	}
	void Insert(int &rt, int v){
		int x = 0, y = 0;
		SplitBySize(rt, v, x, y);
		x = Merge(x, NewPoint(v));
		rt = Merge(x, y);
	}
	void Erase(int &rt, int v){
		int x = 0, y = 0, z = 0;
		SplitBySize(rt, v, x, z);
		SplitBySize(x, v - 1, x, y);
		y = Merge(tr[y].ls, tr[y].rs);//Just delete one
		rt = Merge(Merge(x, y), z); 
	}
	void Rotate(int l, int r){
		int x, y, z;
		SplitBySize(rt, l - 1, x, y);
		SplitBySize(y, r - l + 1, y, z);
		tr[y].tag ^= 1;
		rt = Merge(Merge(x, y), z); 
	}
	void Print(int rt){
		if(!rt) return ;
		PushDown(rt);
		Print(tr[rt].ls);
		printf("%d ", tr[rt].val);
		Print(tr[rt].rs);
	}
}STP;

int n, m;

int main()
{
	n = inpt(), m = inpt();
	rt = 0;
	STP.id = 0;
	for(int i = 1; i <= n; i++){
		STP.Insert(rt, i);
	}
	for(int i = 1; i <= m; i++){
		int l = inpt(), r = inpt();
		STP.Rotate(l, r); 
	}
	STP.Print(rt);
	return 0;
}

It was originally said that I would do my homework if I wrote a little less, but I did not write anything for three hours. It seems that I can't write my homework today. There are too many homework this week. What should I do.

Attached is our dear chemistry teacher. When he knew our physics homework, he drew a crying face beside it (my face laughed rotten)
As for why I suddenly thought of writing this question today, in fact, it is entirely because the first question of today's exam needs to be done with Splay, but our computer room unanimously decided to abandon Splay's scheme and use this better understood and more practical (better back) irrotational Treap to do it. However, we haven't knocked down the balance tree for a long time. (yes, I haven't been alone until now), so I'm going to let today's exam questions go with the wind (write later). Let's write this template question first.

That's it. I wish us success in the chorus competition tomorrow!!!

 

Tags: C++ Algorithm OI programming language

Posted by springo on Sun, 22 May 2022 00:51:18 +0300