文件详细信息

下载本文件

本文件的大小为 3298 字节。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
const int maxn=40000,maxm=40000;
struct MemoryPool{
	char pool[maxn*20],*s=pool;
	void*get(const int n){
		s+=n;
		return s-n;
	}
}Pool;
struct BlockInfo{
	int n,B,tot;
	struct Block{
		int l,r,sum;
	}*b;
	int*arr,*bel;
	void init(const int _n_){
		if(_n_==0){
			n=B=tot=0;
			return;
		}
		n=_n_,B=sqrt(n),tot=(n+B-1)/B;
		b=(Block*)Pool.get(tot*sizeof(Block));
		arr=(int*)Pool.get(n*sizeof(int));
		bel=(int*)Pool.get(n*sizeof(int));
		memset(arr,0,sizeof(int)*n);
		for(int i=0;i<tot;i++){
			b[i].l=i*B,b[i].r=i<tot-1?b[i].l+B-1:n-1,b[i].sum=0;
			for(int j=b[i].l;j<=b[i].r;j++)bel[j]=i;
		}
	}
}info_n,info[maxn+1];
struct Query{
	int l,r,k1,k2,id;
	friend bool operator<(const Query&A,const Query&B){
		return info_n.bel[A.l]!=info_n.bel[B.l]?A.l<B.l:(info_n.bel[A.l]&1)?A.r<B.r:A.r>B.r;
	}
}Q[maxm];
int n,m,a[maxn+1],cnt[maxn+1],ans[maxm];
std::vector<int>bucket[maxn+1],to[maxn+1];
inline void add(const int pos,int x,const int w){
	if(!pos)return;
	info_n.b[info_n.bel[pos]].sum-=bool(info_n.arr[pos]);
	info_n.arr[pos]+=w;
	info_n.b[info_n.bel[pos]].sum+=bool(info_n.arr[pos]);
	x=to[x][pos];
	info[pos].arr[x]+=w;
	info[pos].b[info[pos].bel[x]].sum+=w;
}
inline void add(const int x,const int w){
	add(cnt[x],x,-1);
	add(cnt[x]+=w,x,1);
}
int query(int k1,int k2){
	int i1,i2,j1,j2;
	for(i1=0;info_n.b[i1].sum<k1;i1++)k1-=info_n.b[i1].sum;
	for(i2=info_n.b[i1].l;bool(info_n.arr[i2])<k1;i2++)k1-=bool(info_n.arr[i2]);
	for(j1=0;info[i2].b[j1].sum<k2;j1++)k2-=info[i2].b[j1].sum;
	for(j2=info[i2].b[j1].l;info[i2].arr[j2]<k2;j2++)k2-=info[i2].arr[j2];
	return bucket[i2][j2];
}
int main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=cnt[i];j++)bucket[j].emplace_back(i);
		to[i].reserve(cnt[i]+1);
	}
	for(int i=0,sz;i<=n;i++){
		sz=bucket[i].size();
		for(int j=0;j<sz;j++)to[bucket[i][j]].emplace_back(j);
		info[i].init(sz);
	}
	info_n.init(n);
	read(m);
	for(int i=0;i<m;i++)read(Q[i].l),read(Q[i].r),read(Q[i].k1),read(Q[i].k2),Q[i].id=i;
	std::sort(Q,Q+m);
	memset(cnt+1,0,sizeof(int)*n);
	for(int i=0,l=Q[0].l,r=l-1;i<m;i++){
		while(Q[i].l<l)add(a[--l],1);
		while(r<Q[i].r)add(a[++r],1);
		while(l<Q[i].l)add(a[l++],-1);
		while(r>Q[i].r)add(a[r--],-1);
		ans[Q[i].id]=query(Q[i].k1,Q[i].k2);
	}
	for(int i=0;i<m;i++)write(ans[i]),pc('\n');
	return 0;
}