C++11(clang++ 3.9) 解法, 执行用时: 160ms, 内存消耗: 2916K, 提交时间: 2018-08-02 11:28:51

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
  int x=0,f=1;char ch=getchar();
  while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
  while ('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
  return x*f;
}
const int N=400005;
int n,m,have[N],a[N],ap[N],cnt[N][700],cntk[700],ans[N],pos,bb,blo,L,R;
struct node{int l,r,blo,id,k1,k2;}q[N];
bool operator < (const node &A,const node &B)
{return A.blo<B.blo||A.blo==B.blo&&A.r<B.r;}
void work(int x,int w)
{
  int val=a[x],cc=ap[val];
  if (!--have[cc]) cntk[(cc-1)/bb+1]--;
  cnt[cc][(val-1)/bb+1]--;
  ap[val]+=w;cc=ap[val];
  if (++have[cc]==1) cntk[(cc-1)/bb+1]++;
  cnt[cc][(val-1)/bb+1]++;
}
int qry(int k1,int k2)
{
  int i=1,j;
  while (k1>cntk[i]) k1-=cntk[i],i++;
  for (j=(i-1)*bb+1;j<=i*bb;j++)
    if (have[j])
      if (!--k1) break;
  pos=j;i=1;
  while (k2>cnt[pos][i]) k2-=cnt[pos][i],i++;
  for (j=(i-1)*bb+1;j<=i*bb;j++)
    if (ap[j]==pos)
      if (!--k2) break;
  return j;
}
int main()
{
  n=read();bb=(int)sqrt(n);
  for (int i=1;i<=n;i++) a[i]=read();
  m=read();blo=(int)sqrt(n);
  for (int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].k1=read(),q[i].k2=read(),q[i].id=i,q[i].blo=(q[i].l-1)/blo+1;
  sort(q+1,q+m+1);
  L=1;R=0;
  for (int i=1;i<=m;i++)
  {
    while (L>q[i].l) work(--L,1);
    while (R<q[i].r) work(++R,1);
    while (L<q[i].l) work(L++,-1);
    while (R>q[i].r) work(R--,-1);
    ans[q[i].id]=qry(q[i].k1,q[i].k2);
  }
  for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
  return 0;
}