Tree

Problem B. Tree

Input file: tree.in

Output file: tree.out

Time limit: 2 seconds

Memory limit: 256 megabytes

香香有一棵高度为h的完全二叉树，根节点的标号为1 ，高度为1，对于每个非叶子节点i ，高度h ，它的左儿子的标号为2 * i ，高度为h + 1，它的右儿子的标号为2 * i + 1 ，高度为h + 1。

她的这棵完全二叉树可能有特殊的叶子节点（叶子节点指高度为h的节点）,然而她忘记了特殊叶子节点的标号是什么，但是她有以前无意留下来的q个信息，每个信息包含四个数字H ， L ， R ， Ans ，如果Ans = 1 表示特殊叶子节点的高度为H的祖先属于[L , R],如果Ans = 0 表示不在[L , R]这个区间。（保证[L , R]是高度为H节点标号的子集）

如果没有特殊节点，输出“None.”

如果有唯一特殊节点，输出节点标号。

如果有多个特殊节点，输出“Many.”

注意：有句号，没有引号。

Input

输入包括多组数据，每组数据包括若干行。

对于每组数据：第一行输入两个整数h，q（ h <= 50 , q <= 10^5 ）

接下来q行每行包含四个整数H ， L ， R ， Ans （1 ≤ H ≤ h, 2i - 1 ≤ L ≤ R ≤ 2i - 1, ）

最后一行为两个0，表示输入结束。

Output

对于每组数据，输出一行，如题目描述。

Sample test(s)

input

3 1
3 4 6 0

0 0

output

input

4 3
4 10 14 1
3 6 6 0
2 3 3 1

0 0

output

input

4 2
3 4 6 1
4 12 15 1

0 0

output

Many.

input

4 2
3 4 5 1
2 3 3 1

0 0

output

None.

范围：

对于30% ， q <= 10^3。

对于100% ， q <=10^5 , 数据保证输出不超过3行。

　　对于每个信息，都可以转换为一段叶子节点的取或不取（ans = 0 是不取ans = 1 是取）

　　这样就转化为了区间的交与并。对于30%的数据，很显然，对于每个信息暴力维护当前区间，复杂度n^2 。

　　对于100% ，考虑到如果有多个特殊点并只需输出Many.即可，所以我们把ans = 1 与ans = 0 的分开考虑，ans = 1 直接与原区间求交，ans = 0的单独存下来，于是现在就是在一个连续的区间里挖掉若干块儿，判断是否挖空或者剩下大于1个。想象一下，如果剩余大于一个，那么我们一定有相距最远的两个位置，我们只要知道是否存在两个最远的位置没有被挖掉即可，排序一下就可以了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 int h,q;
 8 struct node{
 9     ll H,L,R,Ans;
10 }Q[200000];
11 int cmp(const node&a,const node&b){
12     if(a.Ans>b.Ans) return 1;
13     if(a.Ans<b.Ans) return 0;
14     if(a.L<b.L) return 1;
15     return 0;
16 }
17 int main(){
18     freopen("tree.in","r",stdin);
19     freopen("tree.out","w",stdout);
20     
21     scanf("%lld%lld",&h,&q);
22     while(h&&q){
23         ll LL=1,RR=1;
24         for(ll i=1;i<=q;i++)
25         scanf("%lld%lld%lld%lld",&Q[i].H,&Q[i].L,&Q[i].R,&Q[i].Ans);
26         for(ll i=1;i<=q;i++){
27             for(ll j=1;j<=h-Q[i].H;j++){
28                 Q[i].L<<=1;
29                 Q[i].R<<=1;
30                 Q[i].R++;
31             }
32         }
33         sort(Q+1,Q+q+1,cmp);
34         for(ll i=1;i<=h-1;i++) LL<<=1;
35         for(ll i=1;i<=h-1;i++) RR<<=1,RR++;
36     
37         ll now=1;
38         while(Q[now].Ans==1){
39             ll nowL=Q[now].L;
40             ll nowR=Q[now].R;
41             if(RR<nowL){
42                 cout<<"None."<<endl;
43             }
44             if(nowR<LL){
45                 cout<<"None."<<endl;
46             }
47             if(LL<=nowL&&RR>=nowR){
48                 LL=nowL;
49                 RR=nowR;
50             }
51             if(LL<=nowL&&RR>=nowL&&nowR>=RR){
52                 LL=nowL;
53                 RR=RR;
54             }
55             if(nowL<=LL&&LL<=nowR&&nowR<=RR){
56                 LL=LL;
57                 RR=nowR;
58             }
59             now++;
60         }
61         for(int i=now;i<=q;i++){
62             if(Q[i].L<=LL&&LL<=Q[i].R){
63                 LL=Q[i].R+1;
64             }
65             if(Q[i].L<=RR&&RR<=Q[i].R){
66                 RR=Q[i].L-1;
67             }
68         }
69         if(LL==RR){
70             printf("%lld
",LL);
71         }
72         else if(LL>RR){
73             cout<<"None."<<endl;
74         }
75         else if(LL<RR){
76             cout<<"Many."<<endl;
77         }
78         scanf("%lld%lld",&h,&q);
79     }
80 
81     return 0;
82 }