题意分析

1. 问题本质
   • 给定一系列区间（海报覆盖的墙段），按顺序贴放，后贴的海报会覆盖之前的海报。
   • 最终需要统计未被完全覆盖的海报数量。

解题思路

从后往前扫描，查询当前$l-r$区间是否已经被完全覆盖，然后将$l~r$覆盖一遍。 我们考虑只把一部分的点放到$set$中以起到跟上述做法同样的效果：类似于离散化，只把每张海报的$l,r,r+1$三个点插入$set$，当$l-r$区间内没有点留在$set$中时，$l-r$区间一定是被完全覆盖了，这样时间复杂度降到了$O(nlogn)$，而且代码量比线段树小非常多。

C++代码实现

#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> PII;
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n); 
        vector<PII> seg(n);
        set<int> left;
        for(int i=0;i<n;i++)
        {
            int l,r;scanf("%d%d",&l,&r);
            seg[i]=(PII){l,r};
            left.insert(l),left.insert(r+1);
        }
        int cnt=0;
        for(int i=n-1;i>=0;i--)
        {
        	int l=seg[i].first,r=seg[i].second;
            if(*left.lower_bound(l)<=r) cnt++;
            while(*left.lower_bound(l)<=r) left.erase(left.lower_bound(l));   
        }                                          
        printf("%d\n",cnt);
    }
    return 0;
}

线段树区间染色模板题，注意要用scanf和printf读入，否则会被卡时间;离散化时注意还要加入l-1,r-1或者l+1,r+1;

int n, m, P, idx, cnt;
int nw[N * 2];
PII w[N / 2];
bool st[N / 2];
map<int, int> mp;

struct Node{
	int l, r;
	int id, tag;
}tr[N * 8];

void push_down(int u){
	if(tr[u].tag){
		tr[lc].id = tr[lc].tag = tr[u].tag;
		tr[rc].id = tr[rc].tag = tr[u].tag;
		tr[u].tag = 0;
	}
}

void build(int u, int l, int r){
	tr[u].l = l, tr[u].r = r, tr[u].id = 0, tr[u].tag = 0;
	if(l == r) return ;
	int mid = tr[u].l + tr[u].r >> 1;
	build(lc, tr[u].l, mid);
	build(rc, mid + 1, tr[u].r);
}

void change(int u, int l, int r, int k){
	if(l <= tr[u].l && r >= tr[u].r){
		tr[u].id = tr[u].tag = k;
		return ;
	}
	push_down(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) change(lc, l, r, k);
	if(r > mid) change(rc, l, r, k);
}

int query(int u, int l, int r){
	if(l <= tr[u].l && r >= tr[u].r){
		return tr[u].id;
	}
	push_down(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) return query(lc, l, r);
	if(r > mid) return query(rc, l, r);
}

void solve()
{
	for(int i = 1; i <= cnt; i ++) st[i] = 0;
	scanf("%d", &n);
	idx = 0; cnt = 0;
	mp.clear();
	for(int i = 1; i <= n; i ++){
		scanf("%d %d", &w[i].x, &w[i].y);
		nw[++ idx] = w[i].x;
		nw[++ idx] = w[i].x - 1;
		nw[++ idx] = w[i].y;
		nw[++ idx] = w[i].y - 1;
	}
	
	sort(nw + 1, nw + idx + 1);
	for(int i = 1; i <= idx; i ++){
		if(mp.find(nw[i]) == mp.end()) mp[nw[i]] = ++ cnt;
	}
	build(1, 1, cnt);
	for(int i = 1; i <= n; i ++){
		int l = mp[w[i].x], r = mp[w[i].y];
		change(1, l, r, i);
	}
	int res = 0;
	for(int i = 1; i <= cnt; i ++){
		int id = query(1, i, i);
		if(!st[id] && id){
			res ++;
			st[id] = 1;
		}
	}
	cout << res << endl;
}