Codeforces 622 C 세그먼트 에 같 지 않 음 (선분 수)
http://codeforces.com/contest/622/problem/C
제목 의 대의:
n 으로 긴 서열, m 개 질문 을 드 립 니 다.매번 한 구간 [l, r] 과 수 x 를 묻는다.이 구간 안에 x 가 아 닌 임의의 위 치 를 물 어보 세 요.
범위:
n,m<=2*10^5。
생각:
선분 수 를 고려 할 수 있 습 니 다.선분 트 리 를 이용 하여 구간 의 최대 값 과 최소 값 을 유지 합 니 다.물 어 볼 때마다 현재 구간 의 최대 값 과 최소 값 이 x 와 다 르 는 지, 다 르 면 왼쪽 트 리 를 먼저 보 세 요. 왼쪽 트 리 위의 최대 최소 값 이 x 와 같다 면 오른쪽 트 리 를 보 세 요.잎 이 맺 힐 때 까지 답 이다. 그렇지 않 으 면 - 1 이다.
코드:
#include
#include
#include
#include
#define M 200005
using namespace std;
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a>1;
if(l==r){
tree[i].ma=tree[i].mi=a[tree[i].l];
return;
}
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
pushup(i);
return;
}
int ans,f;
void query(int l,int r,int i,int z)
{
if(f)return;
if(tree[i].l==tree[i].r){
if(tree[i].ma!=z){f=1;ans=tree[i].l;}
else ans=-1;
return;
}
int mid=tree[i].l+tree[i].r>>1;
if(tree[i].ma!=z||tree[i].mi!=z){
if(r<=mid)query(l,r,i<<1,z);
else if(l>mid) query(l,r,i<<1|1,z);
else {
query(l,mid,i<<1,z);
query(mid+1,r,i<<1|1,z);
}
}
else {
ans=-1;
}
}
int main()
{
int i,j,k,l,r,m,x;
while(~(scanf("%d%d",&n,&m)))
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
while(m--)
{
f=0;
scanf("%d%d%d",&l,&r,&x);
query(l,r,1,x);
printf("%d
",ans);
}
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
