题目连接：

　　

题目大意：

　　有10000000块瓷砖，n张海报需要贴在墙上，每张海报所占的宽度和瓷砖宽度一样，长度是瓷砖长度的整数倍，问按照所给海报顺序向瓷砖上贴海报，最后有几张海报是可见的？

解题思路：

　　因为瓷砖块数和海报张数多，首选线段树，如果按照常规的建树方式，把瓷砖当做数的节点，肯定会MTL.........

所以我们可以用海报的起点和终点当做树的节点，这样树的节点才有20000个，但是这样建树的话，求海报覆盖了那些节点会很复杂，所以我们对每个海报所覆盖的区间也对应建立了一个节点，这样的话线段树有39999个节点。

分析完咯，然后就是建树，还有就是贴海报的时候要倒着贴，这样的话插入海报的时候直接可以判断出来此海报是不是可见。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int maxn = 10005; 7 struct poster 8 { 9     int l, r;10 };11 struct node12 {13     int l, r;14     bool sta;15     int Mid()16     {17         return ( l + r ) / 2;18     }19 };20 node tree[16*maxn];21 poster pos[maxn];22 int hash[maxn*1000], x[maxn*2];23 24 void Build (int root, int l, int r)25 {26     tree[root].l = l;27     tree[root].r = r;28     tree[root].sta = true;29     if (l == r)30         return ;31     Build (2*root+1, l, tree[root].Mid());32     Build (2*root+2, tree[root].Mid()+1, r);33 }34 35 int update (int root, int l, int r)36 {37     if (!tree[root].sta)38         return 0;39     if (tree[root].l == l && tree[root].r == r)40     {41         tree[root].sta = false;42         return 1;43     }44     int x;45     if (r <= tree[root].Mid())46         x = update (2*root+1, l, r);47     else if (tree[root].Mid() < l)48         x = update (2*root+2, l, r);49     else50     {51         int b1 = update (2*root+1, l, tree[root].Mid());52         int b2 = update (2*root+2, tree[root].Mid()+1, r);53         x = b1 || b2;54     }55     if (!tree[2*root+1].sta && !tree[2*root+2].sta)56         tree[root].sta = false;57         return x;58 }59 int main ()60 {61     int t;62     scanf ("%d", &t);63     while (t --)64     {65         int n, num = 0;66         scanf ("%d", &n);67         for (int i=0; i
         
          =0; i--)91             sum += update (0, hash[pos[i].l], hash[pos[i].r]);92                                 printf ("%d\n", sum);93         }94                    return 0;95 }