POJ2528——Mayor's posters

Mayor's posters"/>

POJ2528——Mayor's posters

问题虫洞：Mayor’s posters

推荐博客：【完全版】线段树（转载）

黑洞内窥：

在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报（后面贴的海报覆盖前面的）

思维光年：

离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散化会造成许多错误

代码：

#include<stdio.h>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<string>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
//typedef long long ll;
#define MAXN 100005*8
#define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int
#define MOD 1000000007int tree[MAXN];
int ll[MAXN], rr[MAXN];
bool fs[MAXN];
int xx[MAXN];
int cnt;void pushdown(int node) {if (tree[node] != -1) {tree[node << 1] = tree[node << 1 | 1] = tree[node];tree[node] = -1;}
}void update(int L, int R, int c, int l, int r, int node) {if (L <= l && r <= R) {tree[node] = c;return;}pushdown(node);int m = (l + r) >> 1;if (L <= m) update(L, R, c, l, m, node << 1);if (m < R) update(L, R, c, m + 1, r, node << 1 | 1);
}void query(int l, int r, int node) {if (tree[node] != -1) {if (!fs[tree[node]]) cnt++;fs[tree[node]] = true;return;}if (l == r) return;int m = (r + l) >> 1;query(l, m, node << 1);query(m + 1, r, node << 1 | 1);
}int funn(int key, int n, int xxx[]) {int l = 0, r = n - 1;while (l <= r) {int m = (r + l) >> 1;if (xxx[m] == key) return m;else if (xxx[m] < key) l = m + 1;else r = m - 1;}return -1;
}int main()
{int t, n;cin >> t;while (t--) {scanf("%d", &n);int ans = 0;for (int i = 0; i < n; ++i) {scanf("%d %d", &ll[i], &rr[i]);xx[ans++] = ll[i];xx[ans++] = rr[i];}sort(xx, xx + ans);int m = 1;for (int i = 1; i < ans; ++i) {if (xx[i] != xx[i - 1]) xx[m++] = xx[i];}for (int i = m - 1; i > 0; --i) {if (xx[i] != xx[i - 1] + 1) xx[m++] = xx[i] + 1;}sort(xx, xx + m);memset(tree, -1, sizeof(tree));for (int i = 0; i < n; ++i) {int l = funn(ll[i], m, xx);int r = funn(rr[i], m, xx);update(l, r, i, 0, m, 1);}cnt = 0;memset(fs, false, sizeof(fs));query(0, m, 1);printf("%d\n", cnt);}//system("pause");return 0;
}