题目链接：http://poj.org/problem?id=2528
题意是：给一些海报，有左右端点li，ri，先后贴在墙上，后贴的会覆盖前面贴的，问最后能看到几张海报。
由于li，ri比较大我们离散一下，然后用线段树，对于第i张海报，把[li,ri]修改为i最后看整棵树里有多少个不一样的数字。
离散的时候注意一种情况：
1 10
1 3
5 10
这种情况如果离散为1 4 ，1 2,3 4那么就会出错。我的做法是每两个相差超过1的数字之间，再插一个数字进去。上述情况就会被 离散为1 7 ， 1 3 ，5 7;
#include<cmath> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<stack> #include<queue> #include<iostream> using namespace std; #define LONG long long const int INF=0x3f3f3f3f; const LONG MOD=1e9+61; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) #define EPS 1e-10 #define lson l , mid , rt<< 1 #define rson mid + 1 ,r , (rt<<1)+1 #define root 1, m , 1 int n ; int Num[30100][2] ; int Discret[30010] ; LONG tree[40100] ; int vis[30000]; int RE[51000]; int RE1[51000] ; LONG cov[41000]; void Push_up(int rt) { tree[rt] = tree[rt<<1] + tree[rt<<1|1] ; } void Build_tree(int l , int r , int rt) { cov[rt] = 0 ; if(l == r ) { tree[rt] = 0; return ; } int mid = (l+r)/2 ; Build_tree(lson) ; Build_tree(rson) ; Push_up(rt) ; } void Push_down(int l , int r , int rt) { if(cov[rt]) { int mid = (l +r )/2; cov[rt<<1] = cov[rt] ; cov[rt<<1|1] = cov[rt] ; tree[rt<<1] = (LONG )(mid - l + 1) * cov[rt] ; tree[rt<<1|1] = (LONG ) (r - mid ) * cov[rt] ; cov[rt] = 0 ; } } void Update(int L , int R , int l, int r , int rt ,LONG val ) { if(L <= l && r <= R) { tree[rt] = (LONG )(r - l + 1) * val ; cov[rt] = val ; return ; } int mid = (l + r) /2 ; Push_down( l , r , rt) ; if(L <= mid) Update(L ,R ,lson, val) ; if(R > mid) Update(L ,R ,rson,val) ; Push_up(rt) ; } LONG Query(int L , int R , int l , int r ,int rt) { if(L <= l && r <= R) { return tree[rt] ; } Push_down(l , r , rt) ; LONG res = 0; int mid = ( l + r) /2; if(L <= mid) res += Query( L , R , lson) ; if( R > mid) res += Query(L ,R , rson) ; return res; } int main() { int T; cin>>T; while(T--) { clr0(vis) ; scanf("%d",&n); int m = 0 ; for(int i = 1; i<= n ;++ i) { scanf("%d%d",&Num[i][0] , &Num[i][1]) ; Discret[++m] = Num[i][0] ; Discret[++m] = Num[i][1] ; } sort(Discret + 1 , Discret + m + 1) ; int p = 0; RE1[0] = 0 ; //去重// for(int i =1; i<= m ;++ i) if(RE1[p] != Discret[i]) RE1[++ p] = Discret[i] ; int t = 1; RE[1] = RE1[1] ; //避免离散化时出现问题，每两个相差超过1的数字再插一个数字进去 for(int i = 2 ; i<= p ; ++ i) { if(RE1[i] > RE[t] + 1) RE[t + 1] = RE[t] + 1 ,t++; RE[++t] = RE1[i] ; } sort(RE + 1 , RE + p + 1) ; p = t; // for(int i = 1; i <= p ; ++ i) printf("%d ",RE[i]);cout<<endl; Build_tree( root ) ; for(int i = 1 ; i<= n ;++ i) { Num[i][0] = lower_bound(RE + 1 , RE + p + 1 , Num[i][0]) - RE ; Num[i][1] = lower_bound(RE + 1 , RE + p + 1 , Num[i][1]) - RE ; Num[i][0] += 5 , Num[i][1] += 5 ; Update(Num[i][0] , Num[i][1] , root , i); } // for(int i = 1 ; i <= n ;++ i)printf("%d %d\n",Num[i][0] , Num[i][1]) ; for(int i = 1; i <= p ; ++ i) { LONG tmp = Query(i , i ,root) ; vis[tmp] = 1; } int ans = 0; for(int i = 1; i<= p ; ++i )if(vis[i]) ans ++ ; printf("%d\n",ans); } return 0; }
