# [CodeChefNOV14] Chef and Red Black Tree

## 描述 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.

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

2
1
1
2

CodeChef RBTREE

## 代码 Code

``````#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;
int ans,q;
int main()
{
z=0;
scanf("%d",&q);
while (q--)
{
scanf("%s",ch);
if (ch=='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=='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;
}``````