POJ 2104 K - th Number 문제 풀이 & 코드

뭐 공부 해요?HDU 제목 이랑 똑 같 아 요?아니 야, 아니 야. 이게 다 중 데이터 가 아니 야.http://blog.csdn.net/Rainbow6174/article/details/50374737 사실 포 인 트 는 내 가 왜 계속 TLE 했 는 지 알 게 되 었 다 는 것 이다. map 에 걸 렸 다.

#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
int T,m,n,L,R,K,tot,cnt,line[maxn],vis[maxn],p[maxn],r[maxn];
int tree[maxn*20],son[2][maxn*20],rt[maxn];
void add_tree(int rl,int rn,int l,int r,int value)
{
    tree[rn]=tree[rl]+1;
    if(l==r)return;
    int mid=(l+r)/2;
    if(value>mid)son[0][rn]=son[0][rl],son[1][rn]=++tot,add_tree(son[1][rl],son[1][rn],mid+1,r,value);
    else son[1][rn]=son[1][rl],son[0][rn]=++tot,add_tree(son[0][rl],son[0][rn],l,mid,value);
}
int query(int rl,int rn,int l,int r,int k)
{
    if(l==r)return vis[l];
    int mid=(l+r)/2;
    if(k>tree[son[0][rn]]-tree[son[0][rl]])return query(son[1][rl],son[1][rn],mid+1,r,k-tree[son[0][rn]]+tree[son[0][rl]]);
    else return query(son[0][rl],son[0][rn],l,mid,k);
}
bool cmp(int a,int b)
{
    return line[a]int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&line[i]);
        p[i]=i;
    }
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        vis[i]=line[p[i]];
        r[p[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        rt[i]=++tot;
        add_tree(rt[i-1],rt[i],1,n,r[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&L,&R,&K);
        printf("%d
",query(rt[L-1],rt[R],1,n,K));
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU - 2665 Kth 번호 (주석 트 리 템 플 릿)

Give you a sequence and ask you the kth big number of a inteval. Input The first line is the number of the test cases. F...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

POJ 2104 K - th Number 문제 풀이 & 코드

좋은 웹페이지 즐겨찾기