题解 P3740 【[HAOI2014]贴海报】

题目描述

Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。

张贴规则如下：

• electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；

• 所有张贴的海报的高度必须与electoral墙的高度一致的；

• 每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；

• 后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。

数据范围：

n <= 10000000, m <= 1000, A[i], B[i] <= 10000000

主要思路：珂朵莉树

（珂学盛行！

我们可以直接用珂朵莉树进行assign操作，然后用一个bool类型的数组做桶，直接进行统计，统计过的就不再统计了。

code：

#include <iostream>
#include <cstdio>
#include <set>
#include <stack>
using namespace std;
#define go(i, j, n, k) for(int i = j; i <= n; i += k)
#define mn 100010
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct KDL {
	int l, r; mutable int v;
	KDL(int _l, int _r = -1, int _v = 0) 
		: l(_l), r(_r), v(_v) {}
	bool operator < (const KDL& b) const { return l < b.l; }
};
set<KDL> s;
#define IT set<KDL>::iterator
int n, m; bool b[mn];
inline IT split(int pos) {
	IT it = s.lower_bound(KDL(pos));
	if(it != s.end() && it->l == pos) return it;
	--it;
	int l = it->l, r = it->r, v = it->v;
	s.erase(it);
	s.insert(KDL(l, pos - 1, v));
	return s.insert(KDL(pos, r, v)).first;
} 
inline void assign(int l, int r, int val) {
	IT itr = split(r + 1), itl = split(l);
	s.erase(itl, itr);
	s.insert(KDL(l, r, val));
}
inline int query(int l, int r) {
	IT itr = split(r + 1), itl = split(l);
	int cnt = 0;
	for(IT it = itl; it != itr; ++it) {
//		printf("## : %d %d %d\n", it->l, it->r, it->v);
		if(!b[it->v] && it->v != 0)
			b[it->v] = 1, cnt++;
	}
	return cnt;
}

inline void solve() {
	n = read(), m = read();
	s.insert(KDL(1, n, 0));
	go(i, 1, m, 1) {
		int l = read(), r = read();
		assign(l, r, i);
	}
	cout << query(1, n) << "\n";
}
inline void init() {

}
int main(){
    solve();
    return 0;
}