题目链接:hihocoder1079
【 分析】线段树记录每个点的覆盖海报编号,因为只需要查询一次,最后直接扫描一遍整个线段树计算出有多少个不同的海报编号。
注意:每张海报的区间是一条连续的线段,而一般的线段树只对应离散化的区间上的点,连续型(相当于尺上面的刻度)的[x,y]实际长度为y-x,而离散型(都是真实存在独立的点)的是y-x+1,所以有两种方法解决:
1.用(i,i+1)表示叶子,(x,m)和(m,y)表示左右儿子。
2.把每个连续区间(x,y),改为(x+1,y)或者(x,y-1)。
【AC CODE】238ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <map> //#include <unordered_map> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 200000*2+10; int set[MAXN<<1], tmp[MAXN], pos[MAXN]; struct NODE{ int x,y; }q[MAXN>>1]; inline int id(int x, int y){return x+y|x!=y;} inline void push_down(int x, int y, int m) { int u = id(x,y); if(~set[u]) { int l = id(x,m), r = id(m+1,y); set[l] = set[r] = set[u]; set[u] = -1; } } void update(int x, int y, int ql, int qr, int num) { if(ql <= x && y <= qr) { set[id(x,y)] = num; return; } int m = (x+y)>>1; push_down(x,y,m); if(ql <= m) update(x,m,ql,qr,num); if(qr > m) update(m+1,y,ql,qr,num); } bool vis[MAXN]; void query(int x, int y) { if(x == y) { if(~set[id(x,y)]) vis[set[id(x,y)]] = true; return; } int m = (x+y)>>1; push_down(x,y,m); query(x,m); query(m+1,y); } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int n,L, tol = 0; scanf("%d %d%*c", &n, &L); rep(i,0,n) { scanf("%d %d%*c", &q[i].x, &q[i].y); tmp[tol++] = q[i].x, tmp[tol++] = q[i].y; } tmp[tol++] = L; sort(tmp,tmp+tol); int cnt = 0; pos[cnt++] = tmp[0]; rep(i,1,tol) { if(tmp[i] != tmp[i-1]) pos[cnt++] = tmp[i]; } clc(set,-1); rep(i,0,n) { int x = lower_bound(pos,pos+cnt,q[i].x)-pos, y = lower_bound(pos,pos+cnt,q[i].y)-pos; update(0,cnt-1,x,y-1,i); } clc(vis,0); query(0,cnt-1); int ans = 0; rep(i,0,n) if(vis[i]) ans++; printf("%d\n", ans); return 0; }