　　题目传送门

可怜的狗狗

题目背景

小卡由于公务需要出差，将新家中的狗狗们托付给朋友嘉嘉，但是嘉嘉是一个很懒的人，他才没那么多时间帮小卡喂狗狗。

题目描述

小卡家有N只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。

可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间（i,j）不互相包含。

输入输出格式

输入格式：

第一行输入两个数n，m，你可以假设n<300001 并且 m<50001；m表示他喂了m次。

第二行n个整数，表示第i只狗的漂亮值为ai。

接下来m行，每行3个整数i,j,k表示这次喂食喂第i到第j只狗中第k漂亮的狗的漂亮值。

输出格式：

M行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。

输入输出样例

输入样例#1：

7 2

1 5 2 6 3 7 4

1 5 3

2 7 1

输出样例#1：

3

2

　　分析：

　　$Noip$前复习一波$FHQ\_Treap$。

　　很模板了，求$k$小值，把询问区间排个序再依次处理就行了。

　　Code：

//It is made by HolseLee on 7th Nov 2018

//Luogu.org P1533

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+;

int n,m,tot,root,a[N],ch[N][],val[N],siz[N],p[N],ans[N];

struct Ques {

    int l,r,k,id;

    inline bool operator < (const Ques x) const {

        return l==x.l ? r<x.r : l<x.l;

    }

}q[N];

inline int read()

{

    char ch=getchar(); int x=; bool flag=false;

    while( ch<'' || ch>'' ) {

        if( ch=='-' ) flag=true; ch=getchar();

    }

    while( ch>='' && ch<='' ) {

        x=x*+ch-''; ch=getchar();

    }

    return flag ? -x : x;

}

inline void pushup(int rt)

{

    siz[rt]=siz[ch[rt][]]+siz[ch[rt][]]+;

}

void split(int rt,int k,int &x,int &y)

{

    if( !rt ) x=y=;

    else {

        if( val[rt]<=k ) x=rt, split(ch[rt][],k,ch[rt][],y);

        else y=rt, split(ch[rt][],k,x,ch[rt][]);

        pushup(rt);

    }

}

int merge(int x,int y)

{

    if( !x || !y ) return x+y;

    if( p[x]<p[y] ) {

        ch[x][]=merge(ch[x][],y); pushup(x);

        return x;

    } else {

        ch[y][]=merge(x,ch[y][]); pushup(y);

        return y;

    }

}

inline int neo(int v)

{

    siz[++tot]=; val[tot]=v;

    p[tot]=rand();

    return tot;

}

inline void insert(int v)

{

    int x,y;

    split(root,v,x,y);

    root=merge(merge(x,neo(v)),y);

}

inline void delet(int v)

{

    int x,y,z;

    split(root,v,x,y);

    split(x,v-,x,z);

    z=merge(ch[z][],ch[z][]);

    root=merge(merge(x,z),y);

}

int Rank(int u,int k)

{

    if( siz[ch[u][]]==k- ) return val[u];

    else if( siz[ch[u][]]>=k ) return Rank(ch[u][],k);

    return Rank(ch[u][],k-siz[ch[u][]]-);

}

int main()

{

    srand(time());

    n=read(); m=read();

    for(int i=; i<=n; ++i) a[i]=read();

    for(int i=; i<=m; ++i) {

        q[i].l=read(), q[i].r=read(), q[i].k=read();

        q[i].id=i;

    }

    sort(q+,q+m+);

    int L=, R=;

    for(int i=; i<=m; ++i) {

        while( R<q[i].r ) insert(a[++R]);

        while( L<q[i].l ) delet(a[L++]);

        ans[q[i].id]=Rank(root,q[i].k);

    }

    for(int i=; i<=m; ++i) printf("%d\n",ans[i]);

    return ;

}

巴特西

洛谷P1533 可怜的狗狗 [平衡树，FHQ_Treap]

可怜的狗狗

题目背景

题目描述

输入输出格式

输入输出样例

最新文章

热门文章