可怜的狗狗

Author Avatar
ZC 12月 06, 2018
  • 在其它设备中阅读本文章

题目背景

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

题目描述

小卡家有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

题解

一开始一看就知道是主席树,但是这几天在练treap,所以就想看看能不能用treap写。

想了一下,觉得莫队套treap应该可以,开始我不会指针版的treap,结果mle了。

QwQ

莫队套treap:

#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T> il T
    #define Fur(i,x,y) for(int i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(int i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf (1<<30)
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define l2(n) (ceil(log2(n)))
    il char gc(){static char buf[1000000],*s,*t;return s==t?(((t=(s=buf)+fread(buf,1,1000000,stdin))==s)?-1:*s++) : *s++;}
    //#define gc() getchar()
    il int gi(){int x=0;bool f=0;char c=gc();while(c<'0'||'9'<c){if(c=='-')f=!f;c=gc();}while('0'<=c&&c<='9'){x=x*10+c-48;c=gc();}return f?(-x):x;}
    MB ABS(T x){return x>0?x:-x;}
    MB MAX(T x,T y){return x>y?x:y;}
    MB MIN(T x,T y){return x<y?x:y;}
    MB GCD(T x,T y){return y?GCD(y,x%y):x;}
}using namespace ZDY;using namespace std;
#define N 401001
int sz[N],c[N][2],rs[N],ra[N],w[N];
int cnt=0,rt=0,a[N],n,m,bs,ans[50001];
#define pu(x) sz[x]=sz[c[x][0]]+sz[c[x][1]]+1
il int rand(){
    static int seed=233;
    return seed=(int)seed*482711LL%2147483647; 
}
il void turn(int &x,int p){
    int t=c[x][p];
    c[x][p]=c[t][!p];
    c[t][!p]=x;
    pu(x);pu(x=t);
}
il void ins(int &x,int v){
    if(!x){
        sz[x=++cnt]=1;w[x]=v;ra[x]=rand();
        return;
    }
    sz[x]++;
    int p=(v>w[x]);
    ins(c[x][p],v);
    if(ra[c[x][p]]<ra[x])turn(x,p);
}
il void del(int &x,int v){
    if(w[x]==v){
        if((!c[x][0])||(!c[x][1])){x=c[x][0]+c[x][1];return;}
        int p=(ra[c[x][0]]>ra[c[x][1]]);
        turn(x,p);del(c[x][!p],v);
    }
    else del(c[x][v>=w[x]],v);
    pu(x);
}
il int ask(int x,int k){
    if(sz[c[x][0]]==k-1)return w[x];
    return (sz[c[x][0]]>=k)?ask(c[x][0],k):ask(c[x][1],k-sz[c[x][0]]-1);
}
struct que{
    int l,r,pl,k,id;
}q[50001];
bool cmp(que x,que y){
    if(x.pl!=y.pl)return x.l<y.l;
    return (x.pl&1)?(x.r<y.r):(x.r>y.r);
}
int main(){
    int n=gi(),m=gi();bs=sqrt(n);
    Fur(i,1,n)a[i]=gi();
    int l,r,k;
    Fur(i,1,m){
        l=gi();r=gi();k=gi();
        q[i]=(que){l,r,(l-1)/bs+1,k,i};
    }
    sort(q+1,q+m+1,cmp);
    l=r=1;ins(rt,a[1]);
    Fur(i,1,m){
        Fur(j,l,q[i].l-1)del(rt,a[j]);
        Fdr(j,l-1,q[i].l)ins(rt,a[j]);
        Fur(j,r+1,q[i].r)ins(rt,a[j]);
        Fdr(j,r,q[i].r+1)del(rt,a[j]);
        ans[q[i].id]=ask(rt,q[i].k);
        l=q[i].l;r=q[i].r;
    }
    Fur(i,1,m)printf("%d\n",ans[i]);
}

希望有大佬帮我看看怎么改。QAQ


最后还是乖乖地写了离散化后主席树。

(其实就是模板)

#include<bits/stdc++.h>
namespace ZDY{
    #define res register
    #define ri res ll
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T>
    #define Fur(i,x,y) for(ri i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(ri i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 21474836473
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define l2(n) (ceil(log2(n)))
    MB il T ABS(T x){return x>0?x:-x;}
    MB il T MAX(T x,T y){return x>y?x:y;}
    MB il T MIN(T x,T y){return x<y?x:y;}
    MB il T GCD(T x,T y){return y?GCD(y,x%y):x;}
    //#define gc() getchar()
    il char gc(){static char buf[1000000],*s,*t;return s==t?(((t=(s=buf)+fread(buf,1,1000000,stdin))==s)?-1:*s++) : *s++;}
    il int gi(){int x=0,f=0;char c=gc();while(c<'0'||'9'<c){if(c=='-')f=!f;c=gc();}while('0'<=c&&c<='9'){x=x*10+c-48;c=gc();}return f?(-x):x;}
}using namespace ZDY;using namespace std;
#define N 410011
int s[N*20],ls[N*20],rs[N*20],rt[N],sz=0;
int n,q,a[N],c[N];
struct node{
    int v,pos;
}b[N];
il bool cmp(node x,node y){
    return x.v<y.v;
}
il void build(int &x,int l,int r){
    s[x=++sz]=0;
    if(l==r)return;
    int m=(l+r)>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
il void upd(int &x,int l,int r,int pre,int v){
    x=++sz;
    ls[x]=ls[pre];rs[x]=rs[pre];
    s[x]=s[pre]+1;
    if(l==r)return;
    int m=(l+r)>>1;
    if(v<=m)upd(ls[x],l,m,ls[pre],v);
    else  upd(rs[x],m+1,r,rs[pre],v);
}
il int qh(int x,int y,int l,int r,int k){
    if(l==r)return l;
    int m=(l+r)>>1,cnt=s[ls[y]]-s[ls[x]];
    if(k<=cnt)return qh(ls[x],ls[y],l,m,k);
    return qh(rs[x],rs[y],m+1,r,k-cnt);
}
int main(){
    n=gi(),q=gi();
    Fur(i,1,n)b[i].v=gi(),b[i].pos=i;
    sort(b+1,b+n+1,cmp);
    int d=0,l,r,k;b[0].v=-1000000010;
    Fur(i,1,n)c[a[b[i].pos]=(d+=(b[i].v!=b[i-1].v))]=b[i].v;
    build(rt[0],1,d);
    Fur(i,1,n)upd(rt[i],1,d,rt[i-1],a[i]);
    while(q--)
        l=gi(),r=gi(),k=gi(),
        printf("%d\n",c[qh(rt[l-1],rt[r],1,d,k)]);
}