乒乓游戏

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

　　

Input

　　

Output

　　

Sample Input

　　5

　　1 1 5

　　1 5 11

　　2 1 2

　　1 2 9

　　2 1 2

Sample Output

　　NO

　　YES

HINT

　　

Main idea

　　如果一个区间的端点在区间内，则这个区间可以走到那个区间，询问一个区间能否到另一个区间。

Source

　　首先我们立马想到了：如果两个区间严格有交集，那么这两个区间所能到达的区间集合是一样的。那么如果两个区间严格有交集的话我们就可以把它们合并起来，这里运用并查集。

　　这样处理完之后，剩下的区间只有两种情况：包含或者相离。那么查询的时候显然只要判断两个区间指向的大区间的情况即可。

　　我们要怎么合并呢？显然就是在线段树上进行操作，对于线段树上的每个节点开个vector，存下严格包含这个节点表示的[l,r]的区间的编号，那么我们加入新区间的时候，只要把左右端点在线段树上往下走，如果遇到这个线段树上的节点上的vector有东西，就记录几个区间的最小左端点以及最大右端点，把这几个区间的父亲都指向这个新区间，再删除掉这几个区间即可。然后合并完之后，把得到的新区间再放到各个点的vector进去。

　　最后，由于这题区间端点权比较大，所以要先离散化。

Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std; 10 11 const int ONE=100005*8; 12 const int INF=1e9+1; 13 14 int n; 15 int Num,cnt; 16 17 vector 
              
                Node[ONE]; 18 19 struct power 20 { 21 int l,r,opt; 22 }a[ONE],interval[ONE]; 23 24 int Q[ONE],li_num; 25 struct LISAN 26 { 27 int pos,val; 28 }Li[ONE]; 29 30 int get() 31 { 32 int res=1,Q=1;char c; 33 while( (c=getchar())<48 || c>57 ) 34 if(c=='-')Q=-1; 35 res=c-48; 36 while( (c=getchar())>=48 && c<=57 ) 37 res=res*10+c-48; 38 return res*Q; 39 } 40 41 namespace LI 42 { 43 void add(int i) 44 { 45 if(a[i].opt!=1) return; 46 Num++; 47 Li[++li_num].val = a[i].l; Li[li_num].pos = li_num; 48 Li[++li_num].val = a[i].r; Li[li_num].pos = li_num; 49 } 50 51 int cmp(const LISAN &a,const LISAN &b) { return a.val < b.val;} 52 void Lisan() 53 { 54 sort(Li+1, Li+li_num+1, cmp); 55 56 cnt=0; 57 Li[0].val=-INF; 58 for(int i=1;i<=li_num;i++) 59 { 60 if(Li[i].val!=Li[i-1].val) ++cnt; 61 Q[Li[i].pos]=cnt; 62 } 63 Num=cnt; 64 65 cnt=0; 66 for(int i=1;i<=n;i++) 67 if(a[i].opt==1) 68 a[i].l=Q[++cnt], a[i].r=Q[++cnt]; 69 70 } 71 } 72 73 int fat[ONE]; 74 int Find(int x) 75 { 76 if(fat[x]==x) return x; 77 return fat[x]=Find(fat[x]); 78 } 79 80 namespace Seg 81 { 82 void Delete(int i,int l,int r,int L) 83 { 84 if(Node[i].size()) 85 { 86 for(int j=0; j
               
                >1; 97 if(L <= mid) Delete(i<<1, l, mid, L); 98 else Delete(i<<1|1, mid+1, r, L); 99 }100 101 void Update(int i,int l,int r,int L,int R)102 {103 if(L>R) return;104 if(L<=l && r<=R)105 {106 Node[i].push_back(cnt);107 return;108 }109 int mid=(l+r)>>1;110 if(L<=mid) Update(i<<1,l,mid,L,R);111 if(mid+1<=R) Update(i<<1|1,mid+1,r,L,R);112 }113 }114 115 bool P_edge(power a,power b)116 {117 if( (b.l