hdu 2665 Kth number

제목:링크

방법: 오래 유지할 수 있는 라인 트리

해결:

하나의 서열에 대해 구간의 K가 작은 수는 얼마인지 여러 번 물었다.

트리 커버 트리는 2log이고 쓰기 어려워요!

그래서 우리의 지속 가능한 라인 트리의 우월성은 로그가 하나도 없고 쓰기가 쉽다는 것을 나타낸다.

지난번 문제의 건수와 마찬가지로 물어볼 때 2분의 1로 간단하게 지나갔다.

그러나 이산화 후 서열의 길이는 원래의 n으로 쓰지 않도록 주의해야 한다!!!!!

코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100100
using namespace std;
int a[N];
int uni[N];
struct node
{
    int lson,rson,sum;
}seg[N*20];
int root[N];
int t;
int size;
void build(int l,int r,int &rt)
{
    rt=++size;
    seg[rt].sum=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(l,mid,seg[rt].lson);
    build(mid+1,r,seg[rt].rson);
}
void update(int p,int &q,int l,int r,int v)
{
    q=++size;
    seg[q]=seg[p];
    seg[q].sum++;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(v<=mid)update(seg[p].lson,seg[q].lson,l,mid,v);
    else update(seg[p].rson,seg[q].rson,mid+1,r,v);
}
int que(int L,int R,int l,int r,int k)
{
    if(l==r)return l;
    int mid=(l+r)>>1;
    int tmp=seg[seg[R].lson].sum-seg[seg[L].lson].sum;
    if(tmp>=k)
    {
        return que(seg[L].lson,seg[R].lson,l,mid,k);
    }else
    {
        return que(seg[L].rson,seg[R].rson,mid+1,r,k-tmp);
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        int n,q;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            uni[i]=a[i];
        }
        size=0;
        sort(uni+1,uni+n+1);
        int tot=unique(uni+1,uni+n+1)-uni-1;
        build(1,tot,root[0]);
        for(int i=1;i<=n;i++)
        {
            a[i]=lower_bound(uni+1,uni+1+tot,a[i])-uni;
        }
        for(int i=1;i<=n;i++)
        {
            update(root[i-1],root[i],1,tot,a[i]);
        }
        for(int i=1;i<=q;i++)
        {
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            int debug;
            int j=que(root[l-1],root[r],1,tot,k);
            printf("%d
",uni[j]);
        }
    }
}