hihocoder 1079 (선분 수 + 이산 화)

시간 제한: 1000 ms 단일 시간: 1000 ms 메모리 제한: 256 MB
묘사 하 다.
샤 오 하 이와 소 호 는 귀국 후 7 박 5 일 을 향 한 학생 생활 을 재 개 했 습 니 다. 물론 여러 가지 알고리즘 을 배우 고 있 습 니 다 ~
이날 소 하 이와 소 호가 있 는 학교 에서 동아리 문화 제 를 열 고 각 동아리 가 홍보 란 에 포스터 를 붙 였 지만 붙 여 놓 으 면 다른 동아리 포스터 에 가 려 지 는 포스터 도 있 었 다.이 장면 을 보고 샤 오 하 이 는 이런 의문 이 생 겼 다. 마지막 에 도대체 몇 장의 포스터 가 보일 수 있 을 까?
그래서 소 호 는 이 문 제 를 해결 하 는 책임 을 졌 다. 홍보 란 과 포스터 의 높이 가 똑 같 기 때문에 홍보 란 은 길이 가 L 인 구간 으로 볼 수 있 고 N 장의 포스터 가 순서대로 홍보 란 에 붙 어 있 는데 그 중에서 i 장의 포스터 가 붙 어 있 는 범 위 는 한 구간 [a i, b i] 으로 표시 할 수 있다. 그 중에서 ai, b_i 는 모두 [0, L] 의 정수 에 속 하고 한 장의 포스터 는 볼 수 있 으 며 길이 가 0 보다 큰 일부분 만 나중에 포스터 를 붙 여 가 려 지지 않 았 다.과연 몇 장의 포스터 가 보 일 까?
알림 1: 정확 한 인식 정 보 량 알림 2: 소 하 이 대강당 의 선분 나무의 노드 의미 입력
모든 테스트 포인트 (파일 입력) 가 있 고 테스트 데이터 만 있 습 니 다.각 그룹의 테스트 데이터 의 첫 번 째 행 위 는 두 개의 정수 N 과 L 로 모두 붙 인 포스터 수량 과 홍보 란 의 너 비 를 나타 낸다.각 조 테스트 데이터 의 2 - N + 1 줄 은 붙 인 선후 순서에 따라 한 장의 포스터 를 묘사 하 는데 그 중에서 i + 1 행 위 는 두 개의 정수 ai, b_i. i. 포스터 에 붙 인 구간 은 [a i, b i] 임 을 나타 낸다.100% 의 데이터 에 대해 N < = 10 ^ 5, L < = 10 ^ 9, 0 < = a 만족i,b_i < = L 출력 은 각 그룹의 테스트 데이터 에 대해 하나의 정수 Ans 를 출력 하여 총 몇 장의 포스터 가 보 이 는 지 표시 합 니 다.샘플 입력

5 10
4 10
0 2
1 6
5 9
3 4

샘플 출력 5 문 제 는 빈 벽 을 뜻 하 며 위 에 포스터 를 붙 이 고 포스터 구간 은 (l, r) 이 며 뒤의 것 은 앞 을 덮 고 마지막 에 몇 장 이 보 이 는 지 물 어 봅 니 다.선분 트 리 염색법 이 비교적 전형 적 인 문제 라 고 할 수 있 습 니 다. 각 노드 보존 덕 은 이 구간 의 현재 색상 입 니 다. 문 제 는 전체 구간 의 마지막 색 을 묻 기 때문에 우 리 는 다시 업데이트 한 후에 전체 구간 에 대해 한 번 놀 라 서 물 어보 면 됩 니 다. 작은 tip 는 노드 와 보존 하 는 것 은 구간 색 이 고 모든 것 은 하나의 lazy 배열, node [] 를 따로 열 필요 가 없습니다.레이 지 와 마찬가지 로 바로 아래로 업데이트 하면 됩 니 다. 포스터 마다 색깔 이 다른 숫자 로 표 시 됩 니 다.그리고 주의해 야 할 점 은 포스터 와 한 점 이 아니 기 때문에 나 무 를 만 들 때 잎 노드 가 (l, l + 1) 이지 (l, l) 이 아니 라 (l + 1 = = r) 로 바 뀌 어야 합 니 다. 2 분 에 도 (root < 1, l, mid) 로 나 누 어야 합 니 다. (root ac 코드:

/*
    title:
    description:
    author: averyboy
    time:
    version:
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
const double PI=acos(-1.0);
using namespace std;
int tree[800080];
int ans;
int vis[800080];
int a[100010],b[1000010],c[200020];
map<int,int>mp;
void pushdown(int root)
{
    if(tree[root])
    {
        tree[root<<1]=tree[root];
        tree[root<<1|1]=tree[root];
        tree[root]=0;
    }
    return ;
}
void buildtree(int root,int l,int r)
{
    if(l+1==r)
    {
        tree[root]=0;
        return ;
    }
    int mid=(l+r)>>1;
    buildtree(root<<1,l,mid);
    buildtree(root<<1|1,mid,r);
}
void update(int root,int l,int r,int m,int n,int v)
{
    if(m<=l&&n>=r)
    {
        tree[root]=v;
        //cout<
        return ;
    }
    if(l+1==r)
        return ;
    pushdown(root);
    int mid=(l+r)>>1;
    if(m<=mid)
    update(root<<1,l,mid,m,n,v);
    if(n>=mid)
    update(root<<1|1,mid,r,m,n,v);
}
void query(int root,int l,int r)
{
    if(tree[root]&&!vis[tree[root]])//                  
    {
        vis[tree[root]]=1;
        ans++;
        return ;
    }
    if(l+1==r)
        return ;
    pushdown(root);
    int mid=(l+r)>>1;
    query(root<<1,l,mid);
    query(root<<1|1,mid,r);
}
int main()
{
    int n,l,num,col;
    while(~scanf("%d%d",&n,&l))
    {
        ans=0;
        memset(vis,0,sizeof(vis));
        num=1;
        col=1;
        for(int i=0;iscanf("%d%d",&a[i],&b[i]);
            c[i<<1]=a[i];
            c[i<<1|1]=b[i];
        }
        sort(c,c+2*n);
        for(int i=0;i<2*n;i++)/     
        {
            if(!mp[c[i]])
            {
                mp[c[i]]=num;
                num++;
            }
        }
        buildtree(1,1,num-1);
        for(int i=0;i// cout<
            update(1,1,num-1,mp[a[i]],mp[b[i]],col++);//col        
        }
        query(1,1,num-1);
        cout<return 0;
}