D - Mayor 's posters - 선분 수 구간 덮어 쓰기 + 이산 화

Think: 1 지식 포인트: 선분 수 구간 커버 + 이산 화 2 주제 분석: 경선 자 는 벽 에 홍보 포스터 를 붙 여야 한다. 포스터 의 높이 가 같 고 너비 가 같 지 않 으 며 시간축 에 따라 커버 가 나타난다. 시간축 포스터 의 시작 위치 와 종료 위 치 를 정 하고 최종 상태 에서 얼마나 많은 포스터 를 보 여줄 것 인 지 를 묻는다. n ([1, 10000]), (li, ri) ([1, 10000000]).선배 블 로 그 를 참고 하면 l (ri - li + 1) 과 n 의 차이 가 크기 때문에 이산 화 eg1: 이산 화 전 좌표: [1, 6] [1.7] [2, 10] [8 18] 정렬: 1, 2, 6, 7, 8, 18 이산 화: 1, 3, 4, 6, 7 이산 화 후 좌표: [1, 3] [1, 4] [2, 6] [5, 7] 역 판단 을 해 야 한다.이렇게 하면 현재 노드 구간 이 이미 덮 여 있 는 지 판단 하면 3 반성 할 수 있다. 배열 이 너무 작 게 열 리 지 않도록 주의 하 라.
제목 링크
다음은 Accepted 코드 입 니 다.

/*       +   */
#include 
#include 
#include 

using namespace std;

const int N = 11400;

struct Node{
    int id, x;
}node[N<<1];

struct Tree{
    int l, r, vis;
}tree[N<<3];

int flag;

void Build(int l, int r, int rt);/*    */
void find(int L, int R, int rt);/*        */
void Updata(int rt);/*       */
bool cmp1(struct Node a, struct Node b);
bool cmp2(struct Node a, struct Node b);

int main(){
    int T, n, i, ans;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(i = 1; i <= n<<1; i += 2){
            scanf("%d %d", &node[i].x, &node[i+1].x);
            node[i].id = node[i+1].id = i;
        }
        sort(node+1, node+1+(n<<1), cmp1);
        int pre = 0, cnt = 0;
        for(i = 1; i <= n<<1; i++){/*   */
            if(node[i].x == pre){
                node[i].x = cnt;
            }
            else {
                pre = node[i].x;
                node[i].x = ++cnt;
            }
        }
        Build(1, n<<1, 1);/*2 n——why?*/
        sort(node+1, node+1+(n<<1), cmp2), ans = 0;
        for(i = 1; i <= n<<1; i += 2){/*  ，              */
            flag = 0;
            find(node[i].x, node[i+1].x, 1);
            if(flag) ans++;
        }
        printf("%d
", ans);
    }
    return 0;
}
bool cmp1(struct Node a, struct Node b){
    return a.x < b.x;
}
bool cmp2(struct Node a, struct Node b){
    if(a.id != b.id) return a.id > b.id;
    else return a.x < b.x;
}
void Build(int l, int r, int rt){/*    */
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].vis = 0;
    if(tree[rt].l == tree[rt].r)
        return;
    int mid = (l+r)>>1;
    Build(l, mid, rt<<1);
    Build(mid+1, r, rt<<1|1);
}
void find(int l, int r, int rt){/*        */
    if(tree[rt].vis)
        return;
    if(tree[rt].l == l && tree[rt].r == r){
        tree[rt].vis = 1, flag = 1;
        return;
    }
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(r <= mid)
        find(l, r, rt<<1);
    else if(l > mid)
        find(l, r, rt<<1|1);
    else {
        find(l, mid, rt<<1);
        find(mid+1, r, rt<<1|1);
    }
    Updata(rt);
}
void Updata(int rt){/*       */
    tree[rt].vis = tree[rt<<1].vis & tree[rt<<1|1].vis;
}