POJ - 2104 주석 나무 판자
17975 단어 pojACM_데이터 구조
점 i 를 추가 할 때마다 선분 트 리 root [i] 를 만 듭 니 다. 그러면 선분 트 리 root [r] - root [l - 1] 의 제어 범 위 는 [l, r] 조회 가 k 번 째 로 큽 니 다. 만약 l = r, return l 이 왼쪽 트 리 의 가중치 s 보다 크 면 오른쪽 트 리 k - s 를 조회 합 니 다. 그렇지 않 으 면 왼쪽 트 리 판 자 를 계속 조회 합 니 다.
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+7;
struct node{int l,r,sum;}T[N<<5];
int n,m,cnt;
int root[N],a[N];
vector<int>v;
int id(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int &x,int y,int pos,int l=1,int r=n){
T[++cnt]=T[y],++T[x=cnt].sum;
if(l==r)return;
int mid=(l+r)>>1;
if(mid>=pos)update(T[x].l,T[y].l,pos,l,mid);
else update(T[x].r,T[y].r,pos,mid+1,r);
}
int query(int x,int y,int k,int l=1,int r=n){
if(l==r)return l;
int mid=(l+r)>>1;
int sum=T[T[y].l].sum-T[T[x].l].sum;
if(sum>=k)return query(T[x].l,T[y].l,k,l,mid);
else return query(T[x].r,T[y].r,k-sum,mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",a+i),v.push_back(a[i]);
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;++i)update(root[i],root[i-1],id(a[i]));
while(m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d
",v[query(root[l-1],root[r],k)-1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.