POJ 2528 Mayor's posters——线段树+离散化

POJ 2528 Mayor's posters——线段树+离散化

离散化坑死人

#include #include #include #include using namespace std;const int maxn = 1e5 +10;int T, n, m, segTree[maxn], lazy[maxn], point[maxn], id[10000005];struct Seg { int x, y;}seg[maxn];void init() { memset(segTree, 0, sizeof(segTree)); memset(lazy, 0, sizeof(lazy));}void pushup(int root) { segTree[root] = segTree[root<<1] + segTree[root<<1|1];}void pushdown(int root, int cntL, int cntR) { if (lazy[root]) { lazy[root<<1] = lazy[root<<1|1] = lazy[root]; segTree[root<<1] = lazy[root] * cntL; segTree[root<<1|1] = lazy[root] * cntR; lazy[root] = 0; }}void update_interval(int L, int R, int root, int uL, int uR, int val) { if (uL <= L && R <= uR) { segTree[root] = val * (R - L + 1); lazy[root] = val; return; } int mid = (L + R)>>1; pushdown(root, mid - L + 1, R - mid); if (uL <= mid) { update_interval(L, mid, root<<1, uL, uR, val); } if (uR > mid) { update_interval(mid + 1, R, root<<1|1, uL, uR, val); } pushup(root);}int query(int L, int R, int root, int qL, int qR) { if (qL <= L && R <= qR) { return segTree[root]; } int mid = (L + R)>>1; pushdown(root, mid - L + 1, R - mid); int ans = 0; if (qL <= mid) { ans += query(L, mid, root<<1, qL, qR); } if (qR > mid) { ans += query(mid + 1, R, root<<1|1, qL, qR); } return ans;}int main(){ scanf("%d", &T); while (T--) { scanf("%d", &n); m = 0; for (int i = 0; i < n; i++) { scanf("%d %d", &seg[i].x, &seg[i].y); point[m++] = seg[i].x; point[m++] = seg[i].y; } sort(point, point + m); m = unique(point, point + m) - point; for (int i = 0; i < m; i++) { id[point[i]] = i + 1; } init(); int ans = 0; for (int i = n - 1; i >= 0; i--) { if (query(1, m, 1, id[seg[i].x], id[seg[i].y]) != id[seg[i].y] - id[seg[i].x] + 1) { ans++; update_interval(1, m, 1, id[seg[i].x], id[seg[i].y], 1); } } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。