poj 1769 최소 화 maximizer 단일 업데이트 라인 트 리
1134 단어 데이터 구조
//poj 1769
//sep9
#include
using namespace std;
const int MAXN=100012;
const int MAXX=9999999;
int n,m;
int minv[MAXN*4];
void build(int l,int r,int k)
{
minv[k]=MAXX;
if(l==r)
return ;
int m=(l+r)/2;
build(l,m,2*k);
build(m+1,r,2*k+1);
}
void update(int i,int v,int k,int l,int r)
{
if(minv[k]>v) minv[k]=v;
if(l==r){
return ;
}
int m=(l+r)/2;;
if(i<=m)
update(i,v,2*k,l,m);
else
update(i,v,2*k+1,m+1,r);
}
int query(int from,int to,int k,int l,int r)
{
if(from<=l&&r<=to)
return minv[k];
int m=(l+r)/2;;
if(to<=m)
return query(from,to,2*k,l,m);
else if(from>m)
return query(from,to,2*k+1,m+1,r);
else
return min(query(from,to,2*k,l,m),query(from,to,2*k+1,m+1,r));
}
int main()
{
scanf("%d%d",&n,&m);
build(1,n,1);
update(1,0,1,1,n);
while(m--){
int s,t;
scanf("%d%d",&s,&t);
if(s>=t) continue;
int end=n;//n = t-1,t,...n all acceptable
int v=query(s,end,1,1,n);
update(t,v+1,1,1,n);
}
printf("%d
",query(n,n,1,1,n));
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
