Mayor's posters（线段树+离散化+区间染色）

题目：

题意：将n个区间进行染色（对于同一个区间，后一次染色会覆盖上一次的染色），问最后可见的颜色有多少种。

思路：由于区间长度太大，而n就1e4，假设每次要染色的区间端点值都不相同也就2n，所以我们可以将区间进行离散化，然后对区间进行建树（不是对1，n建树）。我们在节点结构体内部用mx来记录最后这个节点的颜色，flag来标记这个区间内部的颜色是否完全一样，对于一个节点的flag的更新方法为判断它的左右子节点的flag是否都为1（内部颜色完全相同）且左右子节点的颜色是否相同，如果满足这两个条件，那么就将其flag记为1，否则就是0。最后我们用set来维护所有区间的颜色，答案就是set的size。

代码实现如下：

  1 #include <set>
  2 #include <map>
  3 #include <queue>
  4 #include <stack>
  5 #include <cmath>
  6 #include <bitset>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 typedef long long ll;
 17 typedef unsigned long long ull;
 18 
 19 #define lson i<<1,l,mid
 20 #define rson i<<1|1,mid+1,r
 21 #define bug printf("*********
");
 22 #define FIN freopen("D://code//in.txt", "r", stdin);
 23 #define debug(x) cout<<"["<<x<<"]" <<endl;
 24 #define IO ios::sync_with_stdio(false),cin.tie(0);
 25 
 26 const double eps = 1e-8;
 27 const int mod = 1e8;
 28 const int maxn = 1e4 + 7;
 29 const double pi = acos(-1);
 30 const int inf = 0x3f3f3f3f;
 31 const ll INF = 0x3f3f3f3f3f3f3f3f;
 32 
 33 inline int read() {//读入挂
 34     int ret = 0, c, f = 1;
 35     for(c = getchar(); !(isdigit(c) || c == '-'); c = getchar());
 36     if(c == '-') f = -1, c = getchar();
 37     for(; isdigit(c); c = getchar()) ret = ret * 10 + c - '0';
 38     if(f < 0) ret = -ret;
 39     return ret;
 40 }
 41 
 42 set<int> s;
 43 int t, n, ans;
 44 vector<int> v;
 45 
 46 struct s {
 47     int l, r;
 48 }a[maxn];
 49 
 50 struct node {
 51     int l, r, mx, flag;
 52 }segtree[maxn*8];
 53 
 54 void push_down(int i) {
 55     if(segtree[i].flag && segtree[i].l != segtree[i].r) {
 56         segtree[i*2].flag = 1;
 57         segtree[i*2+1].flag = 1;
 58         segtree[i*2].mx = segtree[i].mx;
 59         segtree[i*2+1].mx = segtree[i].mx;
 60         segtree[i].flag = 0;
 61     }
 62 }
 63 
 64 void build(int i, int l, int r) {
 65     segtree[i].l = l, segtree[i].r = r;
 66     segtree[i].mx = -1, segtree[i].flag = 0;
 67     if(l == r) return;
 68     int mid = (l + r) >> 1;
 69     build(lson);
 70     build(rson);
 71 }
 72 
 73 void update(int i, int l, int r, int cur) {
 74     if(segtree[i].l == l && segtree[i].r == r) {
 75         segtree[i].mx = cur;
 76         segtree[i].flag = 1;
 77         return;
 78     }
 79     push_down(i);
 80     int mid = (segtree[i].l + segtree[i].r) >> 1;
 81     if(l > mid) update(i * 2 + 1, l, r, cur);
 82     else if(r <= mid) update(i * 2, l, r, cur);
 83     else {
 84         update(lson, cur);
 85         update(rson, cur);
 86     }
 87     if(segtree[i*2].mx == segtree[i*2+1].mx && segtree[i*2].flag == 1 && segtree[i].flag == 1) {
 88         segtree[i].mx = segtree[i*2].mx;
 89         segtree[i].flag = 1;
 90     } else segtree[i].flag = 0;
 91 }
 92 
 93 void query(int i, int l, int r) {
 94     if(segtree[i].flag) {
 95         if(segtree[i].mx != -1) s.insert(segtree[i].mx);
 96         return;
 97     }
 98     push_down(i);
 99     if(segtree[i].l == segtree[i].r) {
100         if(segtree[i].mx != -1) s.insert(segtree[i].mx);
101         printf("%d %d %d
", segtree[i].l, segtree[i].r, segtree[i].mx);
102         return;
103     }
104     int mid = (segtree[i].l + segtree[i].r) >> 1;
105     query(lson), query(rson);
106 }
107 
108 int main() {
109     //FIN;
110     scanf("%d", &t);
111     while(t--) {
112         scanf("%d", &n);
113         v.clear();
114         s.clear();
115         ans = 0;
116         int m = -1;
117         for(int i = 1; i <= n; i++) {
118             scanf("%d%d", &a[i].l, &a[i].r);
119             v.push_back(a[i].l);
120             v.push_back(a[i].r);
121         }
122         sort(v.begin(), v.end());
123         v.erase(unique(v.begin(), v.end()), v.end());
124         for(int i = 1; i <= n; i++) {
125             a[i].l = lower_bound(v.begin(), v.end(), a[i].l) - v.begin() + 1;
126             m = max(m, a[i].l);
127             a[i].r = lower_bound(v.begin(), v.end(), a[i].r) - v.begin() + 1;
128             m = max(m, a[i].r);
129         }
130         build(1, 1, m);
131         for(int i = 1; i <= n; i++) {
132             update(1, a[i].l, a[i].r, i);
133         }
134         query(1, 1, n);
135         printf("%d
", s.size());
136     }
137     return 0;
138 }