ZOJ 3953 Intervals

线段树，排序。

按照$R$从小到大排序之后逐个检查，如果$L$,$R$最大值不超过$2$，那么就把这个区间放进去，区间$+1$，否则不能放进去。

#include<bits/stdc++.h>
using namespace std;int T,n,sz;
int a[];
struct X { int L,R,id; }s[];
int f[],m[];
int P;bool cmp(X a,X b)
{
    return a.R<b.R;
}int get(int x)
{
    int ll=,rr=sz,res;
    while(ll<=rr)
    {
        int mid = (ll+rr)/;
        if(a[mid]>x) rr=mid-;
        else if(a[mid]==x) return mid;
        else ll=mid+;
    }
}void pushDown(int rt)
{
    if(f[rt]==) return ;
    f[*rt]+=f[rt];
    f[*rt+]+=f[rt];
    m[*rt]+=f[rt];
    m[*rt+]+=f[rt];
    f[rt]=;
}void update(int L,int R,int val,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        f[rt]+=val;
        m[rt]+=val;
        return ;
    }    pushDown(rt);
    int mid = (l+r)/;
    if(L<=mid) update(L,R,val,l,mid,*rt);
    if(R>mid) update(L,R,val,mid+,r,*rt+);
    m[rt] = max(m[*rt],m[*rt+]);
}void query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        P=max(P,m[rt]);
        return ;
    }    pushDown(rt);
    int mid = (l+r)/;
    if(L<=mid) query(L,R,l,mid,*rt);
    if(R>mid) query(L,R,mid+,r,*rt+);
    m[rt] = max(m[*rt],m[*rt+]);
}void build(int l,int r,int rt)
{
    m[rt] = ;
    f[rt] = ;
    if(l==r) return ;    int mid = (l+r)/;
    build(l,mid,*rt);
    build(mid+,r,*rt+);
}int ans[],q;int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        sz=;
        for(int i=;i<=n;i++)
        {
            scanf("%d%d",&s[i].L,&s[i].R);
            sz++; a[sz]=s[i].L;
            sz++; a[sz]=s[i].R;
        }        sort(a+,a++sz);        for(int i=;i<=n;i++)
        {
            s[i].L=get(s[i].L);
            s[i].R=get(s[i].R);
            s[i].id=i;
        }        sort(s+,s++n,cmp);        q=;        build(,sz,);        for(int i=;i<=n;i++)
        {
            P=;
            query(s[i].L,s[i].R,,sz,);
            if(P==)
            {
                ans[q++]=s[i].id;
                continue;
            }
            else update(s[i].L,s[i].R,,,sz,);
        }        sort(ans,ans+q);
        printf("%d\n",q);
        for(int i=;i<q;i++)
        {
            printf("%d",ans[i]);
            if(i<q-) printf(" ");
        }
        printf("\n");    }
    return ;
}