题意： 一共有n张海报， 按次序贴在墙上， 后贴的海报可以覆盖先贴的海报， 问一共有多少种海报出现过。

题解： 因为长度最大可以达到1e7， 但是最多只有2e4的区间个数，并且最后只是统计能看见的不同海报的数目，所以可以先对区间进行离散化再进行区间覆盖的操作。

由于墙上不贴东西的时候对后面没有影响， 所以可以不建树， 直接memset一下就好了。

因为是区域覆盖的问题， 树上原来的点并不会对后面的结果产生影响， 所以可以只修改lazy标记而不对树进行修改。

最后再用建树的操作访问一下lazy标记 并记录答案就好了。

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 #define lson l,m,rt<<1 6 #define rson m+1,r,rt<<1|1 7 #define fi first 8 #define se second 9 const int N = 20000+5;10 int tree[N<<2], lazy[N<<2];11 int a[N];12 bool vis[N];13 int ans, n, t;14 pair
         
           P[N];15 16 void Pushdown(int rt)17 {18     if(lazy[rt])19     {20         lazy[rt<<1|1] = lazy[rt<<1] = lazy[rt];21         lazy[rt] = 0;22     }23 }24 void Revise(int L, int R, int  C ,int l, int r, int rt)25 {26     if(L <= l && r <= R)27     {28         lazy[rt] = C;29         return ;30     }31     Pushdown(rt);32     int m = l+r >> 1;33     if(L <= m) Revise(L,R,C,lson);34     if(m < R)  Revise(L,R,C,rson);35 }36 void build(int l, int r, int rt)37 {38     if(lazy[rt])39     {40         if(!vis[lazy[rt]])41         {42             vis[lazy[rt]] = 1;43             ans++;44         }45         return ;46     } 48     int m = l+r >> 1;49     build(lson);50     build(rson);51 }52 int main()53 {54     ios::sync_with_stdio(false);55     cin.tie(0);56     cout.tie(0);57     cin >> t;58     while(t--)59     {60         ans = 0;61         cin >> n;62         for(int i = 1; i <= 2*n; i++)63         {64             cin >> a[i];65             P[i].fi = a[i], P[i].se = i;66         }67         sort(P+1,P+2*n+1);68         int last = 0, cnt = 0;69         for(int i = 1; i <= 2*n; i++) //离散化操作70         {71             if(P[i].fi == last)72                 a[P[i].se] = cnt;73             else a[P[i].se] = ++cnt, last = P[i].fi;74         }75         memset(lazy, 0, sizeof(lazy));76         for(int i = 1; i <= 2*n; i+=2)77             Revise(a[i],a[i+1],(i+1)/2,1,cnt,1);//由于每次的海报不同所以直接给海报一个编号78         memset(vis, 0, sizeof(vis));79         build(1,cnt,1);80         cout << ans << endl;81     }82     return 0;83 }