POJ - 2528 Mayor’s posters
題目
給出 n 段區間,區間按給出的順序會覆寫掉前面的區間,問最後能看到多少不同的區間。
分析
這題隻需要用到懶惰标記即可,線段樹沒有維護什麼東西,有懶惰标記 c 代表這個區間被 c 覆寫了。
隻不過要用到離散化,題目給出的資料我們隻在乎他們的相對大小,相對大小才會影響到區間覆寫的結果 。
通常離散化的時侯是離散到連續的區間,但是有問題,比如資料:
1 - 10
1 - 4
6 - 10
普通的離散為
1 -> 1
4 -> 2
6 -> 3
10 -> 4
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <set>
#include <algorithm>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 9999991;
const int N = 2e5 + 10;
int t, n, cnt, m, ans;
int a[N], b[N]; //左右區間
int tmp[N]; //離散化數組
int tr[N << 2]; // 線段樹什麼也不維護,隻用到懶惰标記
set<int> s; // 映射關系
void pushdown(int rt){
if(tr[rt] != -1){
tr[rt << 1] = tr[rt << 1 | 1] = tr[rt];
tr[rt] = -1;
}
}
void update(int l, int r, int rt, int L, int R, int c){
if(L <= l && r <= R){
tr[rt] = c;
return;
}
pushdown(rt);
int m = l + r >> 1;
if(L <= m)
update(lson, L, R, c);
if(m < R)
update(rson, L, R, c);
}
void query(int l, int r, int rt){
if(tr[rt] != -1){
if(!s.count(tr[rt])){
ans++;
s.insert(tr[rt]);
}
return;
}
if(l == r)
return;
int m = l + r >> 1;
query(lson);
query(rson);
}
int bi(int key, int n, int *tmp){
int l = 0, r = n - 1;
while(l <= r){
int m = l + r >> 1;
if(tmp[m] == key){
return m;
}
if(tmp[m] < key){
l = m + 1;
}else{
r = m - 1;
}
}
return -1;
}
int main()
{
cin >> t;
while(t--){
cnt = 0;
memset(tr, -1, sizeof(tr)); //開始都沒被染色
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d%d", &a[i], &b[i]);
tmp[cnt++] = a[i];
tmp[cnt++] = b[i];
}
sort(tmp, tmp + cnt);
m = 1;
for(int i = 1; i < cnt; i++){ //去重
if(tmp[i] != tmp[i-1]){
tmp[m++] = tmp[i];
}
}
for(int i = m-1; i > 0; i--){
if(tmp[i] != tmp[i-1]+1){
tmp[m++] = tmp[i - 1] + 1;
}
}
sort(tmp, tmp + m);
// for(int i = 0; i < m; i++){
// cout << tmp[i] << endl;
// }
for (int i = 0; i < n; i++){
int l = bi(a[i], m, tmp);
int r = bi(b[i], m, tmp);
// printf("%d %d\n", l, r);
update(0, m, 1, l, r, i);
}
ans = 0;
s.clear();
query(0, m, 1);
printf("%d\n", ans);
}
return 0;
}