poj2528 线段树+数据离散化

题目传送 poj2528

//#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e6+5;//注意数据范围1 <= li <= ri <= 10000000;开大会爆内存
int a[maxn*3],lazy[maxn*3];
int al[maxn],ar[maxn];//左右区间数组
bool book[maxn*3];//标记数组
void pushdown(int root){ //向下标记
    if(lazy[root]!=-1){
        lazy[root<<1]=lazy[root];
        lazy[root<<1|1]=lazy[root];
        lazy[root]=-1; //记得父节点打回标记
    }
}
void updt(int L,int R,int flag,int l,int r,int root){
    if(L<=l&&R>=r){
        lazy[root]=flag;
        return;
    }
    pushdown(root);
    int mid=(l+r)>>1;
    if(L<=mid)updt(L,R,flag,l,mid,root<<1);
    if(R>=mid+1)updt(L,R,flag,mid+1,r,root<<1|1);
}
int query(int l,int r,int root){
    if(lazy[root]!=-1){ //如果贴了海报，
        if(book[lazy[root]])return 0; //如果没记录看过这张海报
            book[lazy[root]]=true;//标记已经记录看过这张海报
            return 1;       
    }
    if(l==r)
        return 0;
    int mid=(l+r)>>1;
    int ans=0;
    ans+=query(l,mid,root<<1);
    ans+=query(mid+1,r,root<<1|1);
    return ans;
}
int main(){
    int T,N;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        scanf("%d",&N);       
        int tag=0;
        for(int i=1;i<=N;i++){
            scanf("%d%d",&al[i],&ar[i]);
            a[++tag]=al[i];//合并
            a[++tag]=ar[i];
        }
        sort(a+1,a+1+tag);//对合并后的数组排序
        tag=unique(a+1,a+1+tag)-(a+1);//去重
        //注意此处错误，if里面语句修改了循环条件tag的值，导致段错误
        /*for(int i=2;i<=tag;i++){
            if(a[i]!=a[i-1]+1){
                a[++tag]=a[i-1]+1;
            }
        }*/
        for(int i=tag;i>=2;i--){
            if(a[i]!=a[i-1]+1){
                a[++tag]=a[i-1]+1;
            }
        }
        sort(a+1,a+1+tag);
        memset(lazy,-1,sizeof(lazy));
        memset(book,false,sizeof(book));
        for(int i=1;i<=N;i++){
            int l=lower_bound(a+1,a+tag+1,al[i])-a;
            int r=lower_bound(a+1,a+tag+1,ar[i])-a;
            updt(l,r,i,1,tag,1);//把线段当做点来处理，而不是线段的端点
        }   
        printf("%d\n",query(1,tag,1));
    }
    return 0;
}

stl函数介绍:
sort(a+1,a+1+n); 排序，a数组下表从1开始，元素个数为n
unique(a+1,a+1+n)-(a+1); 去重函数,该函数返回a数组去重之后的元素个数,对于无序数组要先进行排序，因为该函数是对相邻元素去重；执行该函数后a数组变为去重之后的数组，它并不真正把重复的元素删除，是把重复的元素移到后面去了，然后依然保存到了原数组中。
运行如下：

unique.png

lower_bound(a+1,a+n+1,key)-a; 找到有序数组中第一个>=key的数的下标
upper_bound(a+1,a+n+1,key)-a;用法与lower_bound一样，但是找到的是有序数组中第一个>key的数的下标
lower_bound函数运行如下：

lower_bound(1).png
边界测试：
lower -bound().png