[CodeChefNOV14] Chef and Red Black Tree

2014-12-17
竞赛题解 / 模拟
CodeChef

描述 Description

Chef likes trees a lot. Today he has an infinte full binary tree (each node has exactly two childs) with special properties.

Chef’s tree has the following special properties :

Each node of the tree is either colored red or black.

Root of the tree is black intially.

Both childs of a red colored node are black and both childs of a black colored node are red.

The root of the tree is labelled as 1. For a node labelled v, it’s left child is labelled as 2v and it’s right child is labelled as 2v+1.

Chef wants to fulfill Q queries on this tree. Each query belongs to any of the following three types:

Qi Change color of all red colored nodes to black and all black colored nodes to red.

Qb x y Count the number of black colored nodes on the path from node x to node y (both inclusive).

Qr x y Count the number of red colored nodes on the path from node x to node y (both inclusive).

Help chef accomplishing this task.

输入格式 InputFormat

First line of the input contains an integer Q denoting the number of queries. Next Q lines of the input contain Q queries (one per line). Each query belongs to one of the three types mentioned above.

输出格式 OutputFormat

For each query of type Qb or Qr, print the required answer.

样例输入 SampleInput

5
Qb 4 5
Qr 4 5
Qi
Qb 4 5
Qr 4 5

样例输出 SampleOutput

2
1
1
2

CodeChef RBTREE

代码 Code

完全二叉树的 LCA 随便搞都行。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
char ch[2];
int ans,q;
int main()
{
    z=0;
    scanf("%d",&q);
    while (q--)
    {
        scanf("%s",ch);
        if (ch[1]=='i') z^=1;
        else
        {
            scanf("%d%d",&x,&y);
            l=r=0;
            while (x!=y)
            {
                if (x>y)
                {
                    x>>=1;l++;
                }
                else
                {
                    y>>=1;r++;
                }
            }
            k=(double)log(x)/(double)log(2);
            t=(k&1)?(z^1):z;
            if (ch[1]=='r')
            {
                if (t) ans=(l>>1)+(r>>1)+1;
                else ans=((l+1)>>1)+((r+1)>>1);
            }
            else
            {
                if (t) ans=((l+1)>>1)+((r+1)>>1);
                else ans=(l>>1)+(r>>1)+1;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}