离散化线段树

int find1(int L,int R,int x)
{
    while(L<=R)
    {
        int m=(L+R)>>1;
        if(a[m]==x)return m;
        else if(a[m]>x)R=m-1;
        else L=m+1;
    }
}

len为最大右值   每次调用数据要转化为二分下标

RI(n);int m;RI(m);

    rep(i,1,m)
    {
        RII(L[i],R[i]);
        a[++cnt]=L[i];
        a[++cnt]=R[i];
    }

    sort(a+1,a+1+cnt);
    len=1;
    rep(i,2,cnt)
    if(a[i]!=a[i-1])a[++len]=a[i];
    repp(i,len,2)
    if(a[i]-a[i-1]>1)a[++len]=a[i]-1;
    sort(a+1,a+1+len);

    rep(i,1,m)
    {
        int l=find1(1,len,L[i]);
        int r=find1(1,len,R[i]);
        update(l,r,i,1,len,1);
    }
原文地址:https://www.cnblogs.com/bxd123/p/10895793.html