给一个1e7的白板，然后有1e5次操作，每次选一段区间，涂上颜色i（会覆盖之前的)。问最后一共可以看到几个颜色。
首先1e7线段树开不下，操作只有1e5，我们考虑离散化。
但是普通离散化不行。比如[1,4] [1,2],[4,4]离散化后为[1,3][1,2],[3,3]。原先第一段没被覆盖，但是离散化后就覆盖了。因为普通的离散化没有反映出不相邻的两个下标的间隔。所以我们在排序后相邻，但是差值不是1的数中间额外插入一个。这样子离散化后就依旧能体现出间隔的作用。
我们接着考虑如何用线段树解决问题，后面的颜色会把前面的颜色覆盖。相当于后面的颜色不会变，我们把过程倒叙就很好处理了。染色过的区域改为false，如果当前这次染色范围内存在true的区域，则当前这次染色可以被人看见，答案加1。并且把整个区域变为false。
无需记录颜色，只要记录true，false就行了。感觉这个记录变量的性质和lzy性质相同，就省去了lzy，但是有点不一样...只有当代码中的ac值为false，也就是要把一整段标为false的时候，ac才有lzy的作用。显然不能ac为true的时候，把孩子又全给成true。然后开始觉得下放标记可以省略，但是发现，存在整段区间标false，然后又被孩子改回来的情况。
随意魔改线段树还是比较容易出错，老老实实的记录lzy标记就好了，为了省一个数组空间....
1 #include <cstdio> 2 #include <map> 3 #include <algorithm> 4 using namespace std; 5 map <int,int> mp; 6 int n,cnt,cnt2,T,ans; 7 bool ac[170000]; 8 int qry[11000][2],vec[21000]; 9 void build(int k,int l,int r) 10 { 11 ac[k] = true; 12 if (l == r) 13 return; 14 int mid = l + r >> 1; 15 build(k << 1,l,mid); 16 build(k << 1 | 1,mid + 1,r); 17 } 18 void down(int k,int l,int r) 19 { 20 if (l == r || ac[k] == true) 21 return; 22 ac[k << 1] = ac[k]; 23 ac[k << 1 | 1] = ac[k]; 24 } 25 void change(int k,int l,int r,int x,int y) 26 { 27 down(k,l,r); 28 if (x <= l && r <= y) 29 { 30 ac[k] = false; 31 return; 32 } 33 int mid = l + r >> 1; 34 if (x <= mid) change(k << 1,l,mid,x,y); 35 if (y >= mid + 1) change(k << 1 | 1,mid + 1,r,x,y); 36 ac[k] = ac[k << 1] || ac[k << 1 | 1]; 37 } 38 bool query(int k,int l,int r,int x,int y) 39 { 40 down(k,l,r); 41 if (x <= l && r <= y) 42 return ac[k]; 43 int mid = l + r >> 1; 44 bool tans = false; 45 if (x <= mid) 46 tans |= query(k << 1,l,mid,x,y); 47 if (y >= mid + 1) 48 tans |= query(k << 1 | 1,mid + 1,r,x,y); 49 return tans; 50 } 51 int main() 52 { 53 for (scanf("%d",&T);T;T--) 54 { 55 cnt = cnt2 = ans = 0; 56 scanf("%d",&n); 57 for (int i = 1;i <= n;i++) 58 { 59 scanf("%d%d",&qry[i][0],&qry[i][1]); 60 vec[++cnt] = qry[i][0]; 61 vec[++cnt] = qry[i][1]; 62 } 63 sort(vec + 1,vec + cnt + 1); 64 cnt = unique(vec + 1,vec + cnt + 1) - (vec + 1); 65 for (int i = 1;i <= cnt;i++) 66 { 67 if (vec[i] != vec[i - 1] + 1) 68 cnt2++; 69 mp[vec[i]] = ++cnt2; 70 } 71 build(1,1,cnt2); 72 for (int i = n;i >= 1;i--) 73 if (query(1,1,cnt2,mp[qry[i][0]],mp[qry[i][1]])) 74 { 75 ans++; 76 change(1,1,cnt2,mp[qry[i][0]],mp[qry[i][1]]); 77 } 78 printf("%d ",ans); 79 } 80 return 0; 81 }