可怜的狗狗
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)]);
}