今天在写线段树的题，在这道题上卡了很久，后来发现是因为离散化有问题，并且线段树的数组开的比较小导致re。

POJ 2528

这道题题意是给你n个区间，每次在区间上涂一种颜色，求出最后剩余颜色数。
由于区间范围1 <= li <= ri <= 10000000 是 1e7 ，所以需要离散化（n最大只有10000） ；

在离散化的时候要注意
1. 保序离散化，大小顺序保持不变。
2. 在离散化超过两个距离（b - a > 1），那么a离散化后的值与b离散化后的值应该相差大于1 ，（如果只差1，那么在中间涂色就无法判断颜色了）。

这样一共有n是 10000 ， 每个线段是有两个端点，那么就是20000 ， 由于最坏情况每个值相差都大于二，那么就是 40000
然后线段树数组应该开最大区间的4倍，所以就是线段树数组应该开 10000 << 4 个;

这里使用懒标记来表示当前区间整个区间颜色是不是同一种颜色

• pushdown的时候，如果当前区间是同一种颜色（懒标记是1），这个区间存储的color有意义，需要传给left和right，把left和right的懒标记置为1（表示当前整个区间是同一种颜色）
• 不需要pushup，因为小区间对大区间没有什么影响，如果想写pushup，可以把pushup写为如果两个儿子都是flag==1，并且color相同，那么就把当前区间color与儿子相同，懒标记置为1，但是这道题不会涂相同的颜色，所以其实不会向上更新
• 在query时，如果当前区间的懒标记是1，或者区间长度是1，就可以把color插入结果，返回了，否则再查找儿子

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>

#define x first
#define y second

using namespace std;

typedef pair<int,int> pii ;
const int N = 1e4 + 100 ;

int n ;
vector<int> stk; //离散化时需要的数组
set<int> s ;   //最后统计有多少种不同颜色
pii a[N] ;     //存储刚开始的区间对
struct node{
    int l,r,col ;
    bool flag ;
}tr[N << 4] ;    //线段树数组

void init(){
    s.clear() ;    //多组数据，初始化
    stk.clear() ;
}

void pushdown(int u){   //向下传递
    node & root = tr[u] ,& left = tr[u << 1] ,& right = tr[u << 1 | 1] ;
    if(root.flag){
        left.col = right.col = root.col ;
        left.flag = right.flag = 1 ;
        root.flag = 0 ;
    }
}

void build(int u,int l,int r){  //初始化线段树，初始化时flag（懒标记）置为1，认为整个区间是无色的
    tr[u] = {l,r,0,1} ;
    if(l != r){
        int mid = l + r >> 1 ;
        build(u << 1 ,l , mid) , build(u << 1 | 1, mid + 1 ,r) ;
    }
}

void modify(int u,int l,int r,int x){   //区间修改
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].col = x ;
        tr[u].flag = 1; 
    }
    else{
        pushdown(u) ;
        int mid = tr[u].l + tr[u].r >> 1; 
        if(l <= mid ) modify(u << 1 ,l , r ,x) ;
        if(r >= mid + 1) modify(u << 1 | 1 ,l , r, x) ;
    }
}

void query(int u,int l,int r){      //查询
    if(tr[u].l == tr[u].r || tr[u].flag){
        if(tr[u].col){
            s.insert(tr[u].col) ;
        }
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) query(u << 1 , l , r) ;
        if(r >= mid + 1 ) query(u << 1 | 1,l ,r) ;
    }
}

int main(){
    int t; 
    cin >> t;
    while(t--){
        cin >> n ;
        init() ;
        for(int i = 1; i <= n ; i++){
            cin >> a[i].x >> a[i].y ;
            stk.push_back(a[i].x) ; 
            stk.push_back(a[i].y) ;
        }

        sort(stk.begin(),stk.end()) ;    //先排序
        int sz = stk.size() ;
        for(int i = 1 ; i < sz ; i++){   //如果找到差值大于1的相邻数，那么插入之间的一个数，保证离散化后值相差大于1
            if(stk[i] - stk[i-1] > 1){
                stk.push_back(stk[i-1] + 1) ;
            }
        }
        sort(stk.begin(),stk.end()) ;   //排序
        stk.erase(unique(stk.begin(),stk.end()),stk.end()) ;  //去重

        build(1,1,stk.size()) ;            //初始化
        for(int i = 1 ; i <= n ; i++){
            a[i].x = lower_bound(stk.begin(),stk.end(),a[i].x) - stk.begin() + 1 ;  //这里把这个数在数组中出现的位置当作离散化的值
            a[i].y = lower_bound(stk.begin(),stk.end(),a[i].y) - stk.begin() + 1 ;
            modify(1,a[i].x,a[i].y,i) ;  //将区间染成 i 颜色
        }
        query(1,1,stk.size()) ;    

        cout << s.size() << "\n" ;  //输出颜色个数
    }
    return 0;
}

再来加一个倒序更新，在查找题解是看到的。
倒序更新思路是，从染色时从后面向前面更新，如果能够把一个没有颜色的格子更新颜色，那么最后会保留该颜色，否则不会，那么每次涂区间时就可以记录是否会留到最后。

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>

#define x first
#define y second

using namespace std;

typedef pair<int,int> pii ;
const int N = 1e4 + 100 ;

int n ;
vector<int> stk; //离散化时需要的数组
pii a[N] ;     //存储刚开始的区间对
struct node{
    int l,r,col ;
}tr[N << 4] ;    //线段树数组

void init(){
    stk.clear() ;
}

void pushup(int u){   //向上传递，如果两个子区间都有颜色，那么就规定该区间有颜色了，只要有了就行，无论是什么
    if(tr[u << 1].col && tr[u << 1 | 1].col){
        tr[u].col = tr[u << 1].col ;
    }
    else{
        tr[u].col = 0 ;
    }
}


void build(int u,int l,int r){  //初始化线段树，初始化时col = 0认为整个区间是无色的
    tr[u] = {l,r,0} ;
    if(l != r){
        int mid = l + r >> 1 ;
        build(u << 1 ,l , mid) , build(u << 1 | 1, mid + 1 ,r) ;
    }
}

bool post(int u,int l,int r,int c){   //染色
    if(tr[u].col){                  //如果刚开始就有颜色，那么肯定染不上，之间返回假
        return false ; 
    }

    if(tr[u].l >= l && tr[u].r <= r){  // 如果整个区间被包含，那么就当作把整个区间染色成c，其实区间内部有过其他颜色也不影响，这里只是是否染色的一种状态
        tr[u].col = c ;
        return true ;
    }
    else{
        bool flag = 0 ;         // 判断是否染色成功
        int mid = tr[u].l + tr[u].r >> 1; 
        if(l <= mid ) flag |= post(u << 1 ,l,r,c) ;  //左染色
        if(r >= mid + 1 ) flag |= post(u << 1| 1, l,r,c) ;  //右染色
        pushup(u) ;   //更新，为下次准备

        return flag ;
    }
}

int main(){
    int t; 
    cin >> t;
    while(t--){
        cin >> n ;
        init() ;
        for(int i = 1; i <= n ; i++){
            cin >> a[i].x >> a[i].y ;
            stk.push_back(a[i].x) ; 
            stk.push_back(a[i].y) ;
        }

        sort(stk.begin(),stk.end()) ;    //先排序
        int sz = stk.size() ;
        for(int i = 1 ; i < sz ; i++){   //如果找到差值大于1的相邻数，那么插入之间的一个数，保证离散化后值相差大于1
            if(stk[i] - stk[i-1] > 1){
                stk.push_back(stk[i-1] + 1) ;
            }
        }
        sort(stk.begin(),stk.end()) ;   //排序
        stk.erase(unique(stk.begin(),stk.end()),stk.end()) ;  //去重

        build(1,1,stk.size()) ;            //初始化
        int cnt = 0 ;
        for(int i = n ; i >= 1 ; i--){
            a[i].x = lower_bound(stk.begin(),stk.end(),a[i].x) - stk.begin() + 1 ;  //这里把这个数在数组中出现的位置当作离散化的值
            a[i].y = lower_bound(stk.begin(),stk.end(),a[i].y) - stk.begin() + 1 ;
            cnt += post(1,a[i].x,a[i].y,i) ;   // 如果能染色，就把统计数加一
        }

        cout << cnt << "\n" ;  //输出颜色个数
    }
    return 0;
}

参考 POJ 2528 Mayor’s posters（线段树区间染色+离散化或倒序更新）