SPOJ/MKTHNUM.cc

   1 #include <cstdio>
   2 #include <algorithm>
   3
   4 using namespace std;
   5
   6 const int maxn=100000+10;
   7
   8
   9 struct node
  10 {
  11         int l,r,sum;
  12         node *lson,*rson;
  13         inline int mid() { return (l+r)>>1; }
  14 } pool[maxn*20],*root[maxn];
  15
  16 int cnt=0,hash[maxn],sorted[maxn],data[maxn];
  17
  18 namespace SegmentTree
  19 {
  20         node* build(int l, int r)
  21         {
  22                 node *k=&pool[cnt++];
  23                 k->l=l,k->r=r,k->sum=0;
  24                 if (l==r) return k;
  25                 int m=k->mid();
  26                 k->lson=build(l,m);
  27                 k->rson=build(m+1,r);
  28                 return k;
  29         }
  30         node* change(node *orig, int x)
  31         {
  32                 node *k=&pool[cnt++];
  33                 *k=*orig;
  34                 k->sum++;
  35                 if (orig->l==x && orig->r==x) return k;
  36                 int m=orig->mid();
  37                 if (x<=m) k->lson=change(orig->lson,x); else
  38                         k->rson=change(orig->rson,x);
  39                 return k;
  40         }
  41         int query(node *left, node *right, int k)
  42         {
  43                 if (left->l==left->r) return left->l;
  44                 int tmp=left->lson->sum-right->lson->sum;
  45                 if (k<=tmp) return query(left->lson,right->lson,k); else
  46                         return query(left->rson,right->rson,k-tmp);
  47         }
  48 }
  49
  50 int main()
  51 {
  52         int n,m;
  53         scanf("%d%d",&n,&m);
  54         int p,i;
  55         for (i=1; i<=n; ++i) scanf("%d",&data[i]),sorted[i]=data[i];
  56         sort(sorted+1,sorted+n+1);
  57         for (p=0,i=1; i<=n; ++i) hash[++p]=sorted[i];
  58         root[0]=SegmentTree::build(1,p);
  59         for (int i=1; i<=n; ++i)
  60         {
  61                 int tmp=lower_bound(sorted+1,sorted+n+1,data[i])-sorted;
  62                 root[i]=SegmentTree::change(root[i-1],tmp);
  63         }
  64         while (m--)
  65         {
  66                 int l,r,k;
  67                 scanf("%d%d%d",&l,&r,&k);
  68                 printf("%d\n",hash[SegmentTree::query(root[r],root[l-1],k)]);
  69         }
  70         return 0;
  71 }