n(n<=10000) 个人依次贴海报, 给出每张海报所贴的范围 li,ri(1<=li<=ri<=10000000) . 求出最后还能看见多少张海报.
虽然之前学过离散化, 但用的时候就想不起来 emm;
10000 个海报 最多有 10000 个区间 20000 个坐标值, 远少于 10000000, 因此采用离散化
将离散化后的坐标对应数组下标储存到线段树中 ;
染色区间是整段的, 本身就可以看做 lazy 标记 , 需要下推函数;
下推 :
- void push_down(int pos){
- if( col[pos]==-1 )return ;
- col[pos<<1]=col[pos<<1|1]=col[pos];
- col[pos]=-1;
- return ;
- }
染色 :
- void updata ( int L ,int R ,int l ,int r,int pos ,int c ){
- if( l>=L && r<=R){
- col[pos] = c;
- return ;
- }
- push_down(pos);
- int mid= (l+r)>>1;
- if( mid>= L) updata ( L ,R ,l ,mid ,pos<<1 ,c);
- if( mid <R) updata( L ,R ,mid+1 ,r ,pos<<1|1 ,c);
- return ;
- }
注意区间的染色情况, 要在各区间坐标之间在增加一个取样;
eg: 线段树 仅采集坐标端点的线段树 1~10 -- 1~3 6~10 --1~1 3~3 6~6 10~10
这样 如 3~6 这个区间之间的颜色就无法判断;
因此要增加离散化取样:
- // 离散化
- for( int i=0; i<n ;i++){
- scanf( "%d%d",&pl[i] ,&pr[i]);
- p[cnt++] = pl[i];
- p[cnt++] = pr[i];
- p[cnt++] = pr[i]+1;
- if( pr[i] - pl[i]>1)p[cnt++] =pl[i]+1;
- }
- sort( p , p+cnt);
- int sz = unique( p ,p+cnt) - p;
查询:
- void query( int L ,int R ,int pos){
- if( col[pos]!=-1 && ! vis[ col[pos]]){
- // cout <<col[pos]<<''<<L<<' '<<R<<endl;
- // cout<< p[L]<<' '<<p[R]<<endl;
- vis [ col[pos] ] = 1;
- ans++;
- return ;
- }
- if( L == R || vis[ col[pos] ])return ; // 最开始只有 L==R 这个 return 条件 结果访问到了不该访问的点 (vis 过但有 col 的点 // push_down(pos); // 如果这里有 push_down 也可以避免上述错误 (在访问端点之前就将其更新, 因此询问时 push_down 可以增加鲁棒性
- int mid =(L +R)>>1;
- query(L ,mid ,pos <<1 );
- query( mid+1 ,R ,pos<<1|1);
- return ;
- }
- #include <cstdio>
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- int pl[10050] ,pr[10050],p[40050];
- int col [160050],vis[160050];
- int ans =0;
- void push_down(int pos){
- if( col[pos]==-1 )return ;
- col[pos<<1]=col[pos<<1|1]=col[pos];
- col[pos]=-1;
- return ;
- }
- void updata ( int L ,int R ,int l ,int r,int pos ,int c ){
- if( l>=L && r<=R){
- // cout<<pos<<" "<<c<<endl;
- col[pos] = c;
- return ;
- }
- push_down(pos);
- int mid= (l+r)>>1;
- if( mid>= L) updata ( L ,R ,l ,mid ,pos<<1 ,c);
- if( mid <R) updata( L ,R ,mid+1 ,r ,pos<<1|1 ,c);
- return ;
- }
- void query( int L ,int R ,int pos){
- if( col[pos]!=-1 && ! vis[ col[pos]]){
- // cout << col[pos]<<''<<L<<' '<<R<<endl;
- // cout<< p[L]<<' '<<p[R]<<endl;
- vis [ col[pos] ] = 1;
- ans++;
- return ;
- }
- if( L == R || vis[ col[pos] ])return ; // 上面下面任选其一即可
- // push_down(pos);
- int mid =(L +R)>>1;
- query(L ,mid ,pos <<1 );
- query( mid+1 ,R ,pos<<1|1);
- return ;
- }
- int bond( int n ,int x ,int y ){
- int mid = x+(y-x)/2 ;
- while( p[mid] != n ){
- if( p[mid]> n){
- y = mid;
- }
- if( p[mid] <n){
- x= mid+1;
- }
- mid = x+(y-x)/2 ;
- }
- return mid;
- }
- int main( ){
- freopen( "out.txt" ,"w",stdout);
- int T;
- int n;
- scanf( "%d",&T );
- while ( T--){
- memset( col ,-1 ,sizeof(col));
- memset( vis , 0 ,sizeof(vis));
- scanf("%d",&n);
- int cnt=0;
- for( int i=0; i<n ;i++){
- scanf( "%d%d",&pl[i] ,&pr[i]);
- p[cnt++] = pl[i];
- p[cnt++] = pr[i];
- p[cnt++] = pr[i]+1;
- if( pr[i] - pl[i]>1)p[cnt++] =pl[i]+1;
- }
- sort( p , p+cnt);
- int sz = unique( p ,p+cnt) - p;
- // for( int i=0 ;i<sz ;i++)cout << p[i]<<" ";
- // cout<<endl;
- for( int i=0 ; i<n ;i++){
- int l= upper_bound(p ,p+sz ,pl[i])-p;
- int r= upper_bound(p ,p+sz ,pr[i])-p;
- // cout<<l<<" "<<r<<endl;
- updata(l, r, 1 ,sz , 1, i+1);
- }
- // for( int i=1 ;i<= 12 ;i++)cout <<col[i]<<" ";
- ans= 0;
- query( 1 , sz ,1);
- printf( "%d\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3002840.html