[문제] [구간 트 리 / set] NKOJ 3480 [2015 다 교 합동 훈련 2] 아 Q 의 주차장
문 제 는 운전 면 허 를 갓 따 낸 KJ 가 항상 차 를 몰 고 드라이브 하 는 것 을 좋아한다 고 설명 했다. 놀다 가 아 Q 주차장 에 차 를 세 웠 다. 그녀 는 자신의 주차 수준 에 자신 이 있 지만 다른 사람의 주차 수준, 특히 Kelukin 을 안심 하지 못 했다.그래서 그녀 는 매번 자신의 사랑 의 차 를 다른 차 에서 가장 먼 곳 에 세 웠 다.KJ 는 자신의 이런 전략 이 매우 과학적 이 라 고 생각 하여 주차장 에 좌석 이 하나 있 는데 왼쪽 에서 오른쪽 까지 번호 가 1 부터 n 이 고 처음에 모두 비어 있 었 다 고 생각 하기 시작 했다.몇 개의 자동차 가 있 는데, 주차장 을 드 나 드 는 것 은 모두 m 회 이다.주차장 에 들 어 가 는 모든 자동차 에 대해 서 는 다른 차 와 의 거리 가 가장 작은 차 를 선택 하고 조건 에 맞 는 여러 개가 있 으 면 가장 왼쪽 하 나 를 선택한다.KJ 는 생각 하 다가 잠 이 들 었 습 니 다. 옆 에 있 는 Kelukin 은 그녀의 소원 을 들 어 주 려 고 했 습 니 다. 그러나 그 는 매우 게 을 러 서 스스로 손 을 쓰 려 고 하지 않 았 습 니 다. 그래서 이 문 제 를 당신 에 게 남 겨 주 었 습 니 다. KJ 의 이상 적 인 아 Q 주차장 에서 당신 의 차량 이 드 나 드 는 조작 서열 을 주 고 모든 차 의 좌석 번 호 를 차례대로 졌 습 니 다.
형식 첫 줄, 두 정수 n 과 m 를 입력 하여 주차장 크기 와 조작 수 를 표시 합 니 다.다음 m 줄 에서 각 줄 의 정수 F 와 x F 는 1 로 번호 가 x 인 차 가 주차장 에 들 어 가 는 것 을 나타 낸다.F 는 2 로 번호 가 x 인 차 가 주차장 밖으로 나 간 다 는 뜻 이다.합 법 적 인 조작 을 보장 한다. 즉, 주차장 을 나 가 는 차 는 반드시 현재 주차장 에 있다.주차장 안의 차 는 n 을 초과 하지 않 는 다.
출력 형식 은 모든 조작 1 에 대해 정 수 를 출력 하여 이 차 의 번 호 를 표시 합 니 다.
샘플 입력 7 11 1 15 1 123123 1 3 1 5 2 123123 2 15 1 21 2 3 1 6 1 7 8
샘플 출력 1, 7, 4, 2, 7, 4, 1, 3.
제시 [데이터 범위] 대 30% 의 데이터 n < = 1000, m < = 1000 대 60% 의 데이터 n < = 20000, m < = 2000 대 100% 의 데이터 n, m < = 20000, 차 의 번 호 는 10 ^ 6 보다 작 습 니 다.
출처: BS
사고: 법 1: 선분 나무, 1. 유지 보수 단점 1 또는 0 은 주차 여 부 를 나타 낸다.왼쪽 에서 오른쪽으로 얻 을 수 있 는 가장 효과 적 인 구간, 오른쪽 에서 왼쪽으로 얻 을 수 있 는 가장 효과 적 인 구간, 전체 얻 을 수 있 는 가장 효과 적 인 구간 을 유지 합 니 다.2. 유효 구간 정의: 첫 번 째 키워드: 주차 후 가장 가 까 운 차 와 의 거 리 는 클 수록 좋다.두 번 째 키워드: 왼쪽 점 의 위 치 는 작 을 수록 좋다.세 번 째 키워드: 구간 총 길이, 길 수록 좋 습 니 다.3. 조작 조작 1. 1 시작 구간, n 끝 구간, max 구간 에서 누가 b 의 위 치 를 얻 을 수 있 는 지 판단 한다 (첫 번 째, 꼬리 구간 이 특수 하 다).조작조작 2, 점 조작 0.
#include
');
}
//....................................................
struct yf
{
int a,b;
inline int loc(){return (a+b)>>1;}
inline int len(){return b-a+1;}
inline int len2(){return loc()-a+1;}
inline friend bool operator>(yf a,yf b)
{
if(a.len2()==b.len2())
{
if(a.a==b.a) return a.len()>b.len();
return a.areturn a.len2()>b.len2();
}
inline yf operator+(const yf& b)
{
yf ans;
ans.a=a,ans.b=b.b;
return ans;
}
};
struct fy
{
int a,b,val;
yf fl,fr,max;
inline int len(){return b-a+1;}
} w[need<<3];
#define ls (s<<1)
#define rs ((s<<1)|1)
inline void NBHB(int s)
{
if(w[s].len()==1)
{
if(w[s].val==0)
{
w[s].fl.b=w[s].a;
w[s].max=w[s].fr=w[s].fl;
}
else
{
w[s].fl.b=w[s].a-1;
w[s].fr.a=w[s].b+1;
w[s].max=w[s].fl;
}
return ;
}
if(w[rs].max>w[ls].max) w[s].max=w[rs].max;
else w[s].max=w[ls].max;
if(w[ls].fr+w[rs].fl>w[s].max) w[s].max=w[ls].fr+w[rs].fl;
if(w[ls].len()==w[ls].fl.len())
{
w[s].fl.b=w[ls].a+w[ls].fl.len()+w[rs].fl.len()-1;
}
else w[s].fl.b=w[ls].fl.b;
if(w[rs].len()==w[rs].fr.len())
{
w[s].fr.a=w[rs].b-w[rs].fr.len()-w[ls].fr.len()+1;
}
else w[s].fr.a=w[rs].fr.a;
}
void build(int s,int l,int r)
{
w[s].a=w[s].fl.a=l,w[s].b=w[s].fr.b=r;
if(l==r)
{
w[s].val=0;
NBHB(s);
return ;
}
build(ls,l,(l+r)>>1),build(rs,(l+r)/2+1,r);
NBHB(s);
}
int d,val;
int loc[needk];
inline void change(int s)
{
if(w[s].len()==1)
{
w[s].val=val;
NBHB(s);
return ;
}
int mid=(w[s].b+w[s].a)>>1;
if(d<=mid) change(ls);
else change(rs);
NBHB(s);
}
//....................................................
int main()
{
int n,m;scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1,a,b,lenl,lenr,lenm,temploc,templen;i<=m;i++)
{
in_(a),in_(b);
if(a==1)
{
temploc=w[1].max.loc();
lenm=templen=w[1].max.len2();
lenl=w[1].fl.len();
lenr=w[1].fr.len();
if(lenl>=lenm) temploc=1,templen=lenl;
if(lenr>templen) temploc=n;
loc[b]=temploc;
out_(loc[b]);//printf("%d
",loc[b]);
d=loc[b],val=1;
change(1);
}
else
{
d=loc[b],val=0;
change(1);
loc[b]=0;
}
}
} 법 2: set 는 조작 1 에 대해 매번 가장 효과 적 인 구간 만 선택 하고 set 또는 우선 대기 열 을 사용 하 는 것 을 고려 합 니 다.한 점 을 삭제 하면 두 구간 으로 변 한다. 즉, 하 나 를 삭제 하고 두 개 를 추가 하 는 것 이다.조작 2 에 대해 서 는 매번 두 구간 을 합 쳐 야 한다. 즉, 두 개 를 삭제 하고 하 나 를 추가 해 야 한다.지정 한 구간 을 삭제 하기 위해 서 는 우선 대기 열 이 아 닌 set 를 사용 합 니 다.
또 하나의 set 를 열 어 주차 한 위 치 를 순서대로 기록 하여 합병 할 때 합병 해 야 할 두 구간 을 쉽게 찾 을 수 있 습 니 다.
#includereturn a.len()>b.len();
} };
typedef set
",loc_[b]=ans);
loc.insert(ans);
}
else
{
lit=loc.find(loc_[b]);
temp.a=*(--lit)+1,temp.b=loc_[b]-1;
s.erase(temp);
temp1.a=loc_[b]+1,temp1.b=*(++++lit)-1;
s.erase(temp1);
temp.b=temp1.b;
s.insert(temp);
loc.erase(loc_[b]);// erasse
loc_[b]=0;
}
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
자바 - 숫자 반전이 수의 각 비트 에 있 는 숫자 를 반전 시 켜 새 수 를 얻 으 십시오.새 수도 정수 의 흔 한 형식 을 만족 시 켜 야 한다. 입력 형식: 총 1 줄, 정수 N 을 입력 하 십시오.출력 형식: 출력 총 1 줄,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
