记录编号	422021	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	2.006 s
提交时间	2017-07-08 18:21:05	内存使用	1.58 MiB

# include <bits/stdc++.h>
# define MAXN 100003
# define mid ((l + r) >> 1)
using namespace std;

char buf[1 << 18], *fs, *ft;

char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);

inline char getc() { 
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int gn() { 
    int k = 0, f = 1;
    char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}

inline void out() { 
    fwrite(ops, 1, opt - ops, stdout);
    opt = ops;
}

inline void out(int x) { 
    static char *p = new char[21]();
    *(++p) = '\n';
    do { 
        *(++p) = x % 10 | 0x30;
        x /= 10;
    } while(x);
    while(*p) { 
        *(opt++) = *(p--);
        if(opt == opt_end) out();
    }
}

int n, m, a[MAXN], mina = 0x7fffffff, maxa;

struct node{ 
    int sum;
    node *ls, *rs;
}*root[MAXN];

node *build(int l, int r) { 
    node *x = new node();
    if(l ^ r) { 
        x->ls = build(l, mid);
        x->rs = build(mid + 1, r);
    }
    return x;
}

node *add(node *pre, int l, int r, int p) { 
    node *x = new node();
    if(l ^ r) { 
        if(p <= mid) { 
            x->ls = add(pre->ls, l, mid, p);
            x->rs = pre->rs;
        } else { 
            x->rs = add(pre->rs, mid + 1, r, p);
            x->ls = pre->ls;
        }
        x->sum = x->ls->sum + x->rs->sum;
    } else { 
        x->sum = pre->sum + 1;
    }
    return x;
}

int query(node *s, node *t, int l, int r, int k) { 
    if(l ^ r) { 
        int tmp = t->ls->sum - s->ls->sum;
        if(tmp < k) 
            return query(s->rs, t->rs, mid + 1, r, k - tmp);
        else 
            return query(s->ls, t->ls, l, mid, k);
    } else return l;
}

int main() { 
# ifndef LOCAL
    freopen("kth.in", "r", stdin);
    freopen("kth.out", "w", stdout);
# else 
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
# endif
   n = gn(), m = gn();
   for(int i = 1; i <= n; i++) { 
        a[i] = gn();
        mina = min(mina, a[i]);
        maxa = max(maxa, a[i]);
   }
   root[0] = build(mina, maxa);
   for(int i = 1; i <= n; i++) { 
      root[i] = add(root[i - 1], mina, maxa, a[i]);
   }
   for(int i = 1; i <= m; i++) { 
       int l =gn(), r = gn(), k =gn();
       out(query(root[l - 1], root[r], mina, maxa, k));
   }
   out();
}