[jzoj 4845] [찾기] [선분 수]

제목 의 대의
이것 은 2 차원 평면 세계 입 니 다. 평면 에 n 개의 특수 한 열매 가 있 습 니 다. 저 는 (0, 0) 점 에서 출발 하여 가능 한 한 많은 열 매 를 얻 고 싶 습 니 다. 그러나 특정한 특수 한 원인 으로 인해 제 운동 방식 은 세 가지 밖 에 없습니다 (현재 제 가 (x, y).
1. 갈 수 있어 요 (x + 1, y)
2. 나 는 갈 수 있다 (x, y + 1)
3. 저 는 걸 어 갈 수 있 습 니 다 (x + 1, y + 1)
지금 나 는 너의 도움 이 필요 하 다. 내 가 가장 많은 열 매 를 얻 을 수 있 는 지 찾 아 줘.
문제 풀이 의 사고 방향.
먼저 x 를 첫 번 째 키워드 로 정렬 하고 y 는 두 번 째 키워드 로 정렬 합 니 다. 분명히 한 점 은 오른쪽 위 에 만 갈 수 있 습 니 다. x 에 따라 정렬 되 었 기 때문에 선분 트 리 로 높이 에서 가장 좋 은 값 을 유지 하면 됩 니 다. 구간 수정 단점 조회.
code

#include
#include
#include
#include
#include
#include
#define LL long long
#define LD double
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const inf=2147483647;
int const maxn=100000,maxy=1000000001;
int n,cnt,pon=1,t[maxn*50+10],lson[maxn*50+10],rson[maxn*50+10];
struct rec{
    int x,y;
    friend bool operatorx,rec y){
        return (x.x<y.x)||((x.x==y.x)&&(x.y<y.y));
    }
};
rec a[maxn+10];
void pushtag(int pos){
    lson[pos]=(!lson[pos])?(++pon):lson[pos];
    t[lson[pos]]=max(t[lson[pos]],t[pos]);
    rson[pos]=(!rson[pos])?(++pon):rson[pos];
    t[rson[pos]]=max(t[rson[pos]],t[pos]);
    t[pos]=0;
}
int qury(int pos,int l,int r,int v){
    if(l!=r)pushtag(pos);
    else return t[pos];
    int mid=(l+r)/2;
    if(v<=mid)return qury(lson[pos],l,mid,v);
    else return qury(rson[pos],mid+1,r,v);
}
void change(int pos,int l,int r,int ll,int rr,int v){
    if(l!=r)pushtag(pos);
    int mid=(l+r)/2;
    if((l==ll)&&(r==rr)){
        t[pos]=max(t[pos],v);
        return;
    }else if(rr<=mid){
        change(lson[pos],l,mid,ll,rr,v);
    }else if(midpos],mid+1,r,ll,rr,v);
    }else{
        change(lson[pos],l,mid,ll,mid,v);
        change(rson[pos],mid+1,r,mid+1,rr,v);
    }
}
int main(){
    freopen("find.in","r",stdin);
    freopen("find.out","w",stdout);
    scanf("%d",&n);
    fo(i,1,n){
        int x,y;scanf("%d%d",&x,&y);
        if((x>=0)&&(y>=0)){
            cnt++;
            a[cnt].x=x;a[cnt].y=y+1;
        }
    }
    sort(a+1,a+cnt+1);
    int ans=0;
    fo(i,1,cnt){
        int tmp=qury(1,1,maxy,a[i].y)+1;
        ans=max(ans,tmp);
        change(1,1,maxy,a[i].y,maxy,tmp);
    }
    printf("%d",ans);
    return 0;
}