題意為求一個(gè)給定區(qū)間[s,e]內(nèi)的第k小元素。
這里用到一種新的數(shù)據(jù)結(jié)構(gòu)，叫做劃分樹。網(wǎng)上介紹很多了，我就不多說(shuō)了。
不過(guò)我對(duì)這種結(jié)構(gòu)有點(diǎn)小體會(huì)：
可以當(dāng)作線段樹來(lái)理解，但是查詢操作是基于有多少元素被劃分到左區(qū)間來(lái)定位的。而在查詢操作中給出的[s,e]并不是區(qū)間[s,e]，而是該區(qū)間內(nèi)第s到第e個(gè)元素
代碼寫的有點(diǎn)搓。。有時(shí)間重寫下。。
1 import java.io.*;
2 import java.util.Arrays;
3 class node
4 {
5 int s,e;
6 int num[],count[];
7 }
8 public class Main {
9
10 /**
11 * @param args
12 */
13 static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
14 static int readInt() throws IOException
15 {
16 in.nextToken();
17 return (int)in.nval;
18 }
19 static node st[];
20 static int data[];
21 static void make(int pos)
22 {
23 int s=st[pos].s,e=st[pos].e;
24 if(s!=e)
25 {
26 int mid=(s+e)/2;
27 st[pos<<1].s=s;
28 st[pos<<1].e=mid;
29 st[pos<<1].num=new int[mid-s+1];
30 st[pos<<1].count=new int[mid-s+1];
31 st[(pos<<1)+1].s=mid+1;
32 st[(pos<<1)+1].e=e;
33 st[(pos<<1)+1].num=new int[e-mid];
34 st[(pos<<1)+1].count=new int[e-mid];
35 int c1=0,c2=0;
36 for(int i=s;i<=e;i++)
37 {
38 if(st[pos].num[i-s]<=data[mid])
39 {
40 st[pos<<1].num[c1++]=st[pos].num[i-s];
41 st[pos].count[i-s]=(i==s?0:st[pos].count[i-s-1])+1;
42 }
43 else
44 {
45 st[(pos<<1)+1].num[c2++]=st[pos].num[i-s];
46 st[pos].count[i-s]=(i==s?0:st[pos].count[i-s-1]);
47 }
48 }
49 make(pos<<1);
50 make((pos<<1)+1);
51 }
52 }
53 static int find(int s,int e,int k,int pos)
54 {
55 if(st[pos].s==st[pos].e) return st[pos].num[s];
56 int left=st[pos].count[e]-(s==0?0:st[pos].count[s-1]);
57 if(k<=left)
58 return find(s==0?0:st[pos].count[s-1],st[pos].count[e]-1,k,pos<<1);
59 else
60 return find(s==0?0:s-st[pos].count[s-1],e+1-st[pos].count[e]-1,k-left,(pos<<1)+1);
61
62 }
63 public static void main(String[] args) throws IOException{
64 int n=readInt(),q=readInt();
65 st=new node[4*n];
66 for(int i=0;i<st.length;i++)
67 st[i]=new node();
68 st[1].num=new int[n];
69 st[1].count=new int[n];
70 for(int i=0;i<n;i++)
71 st[1].num[i]=readInt();
72 data=st[1].num.clone();
73 Arrays.sort(data);
74 st[1].s=0;
75 st[1].e=n-1;
76 make(1);
77 while((q--)!=0)
78 System.out.println(find(readInt()-1,readInt()-1,readInt(),1));
79
80 }
81
82 }
83