区间第K大(划分树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
const int N = 100005;

int sorted[N];
int Tree[20][N];
int toLeft[20][N];

void Build(int k,int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    int i,t;
    t=mid-l+1;
    for(i=l;i<=r;i++)
       if(Tree[k][i]<sorted[mid])
          t--;
    int L=l;
    int R=mid+1;
    for(i=l;i<=r;i++)
    {
       if(i==l)
          toLeft[k][i]=0;
       else
          toLeft[k][i]=toLeft[k][i-1];
       if(Tree[k][i]<sorted[mid])
       {
           toLeft[k][i]++;
           Tree[k+1][L++]=Tree[k][i];
       }
       else if(Tree[k][i]>sorted[mid])
       {
           Tree[k+1][R++]=Tree[k][i];
       }
       else
       {
           if(t!=0)
           {
               t--;
               toLeft[k][i]++;
               Tree[k+1][L++]=Tree[k][i];
           }
           else
               Tree[k+1][R++]=Tree[k][i];
       }
    }
    Build(k+1,l,mid);
    Build(k+1,mid+1,r);
}

int Query(int k,int l,int r,int p,int q,int t)
{
    if(p==q) return Tree[k][p];
    int s,ss;
    int mid=(l+r)>>1;
    if(l==p)
    {
        s=0;
        ss=toLeft[k][q];
    }
    else
    {
        s=toLeft[k][p-1];
        ss=toLeft[k][q]-s;
    }
    int L,R;
    if(t<=ss)
    {
        L=l+s;
        R=l+s+ss-1;
        return Query(k+1,l,mid,L,R,t);
    }
    else
    {
        L=mid-l+1+p-s;
        R=mid-l+1+q-s-ss;
        return Query(k+1,mid+1,r,L,R,t-ss);
    }
}

int main()
{
    int n,m,i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&Tree[0][i]);
            sorted[i]=Tree[0][i];
        }
        std::sort(sorted+1,sorted+n+1);
        Build(0,1,n);
        scanf("%d",&m);
        int p,q,k;
        while(m--)
        {
            scanf("%d%d%d",&p,&q,&k);
            p++;q++;k--;
            printf("%dn",Query(0,1,n,p,q,q-p+1-k));
        }
    }
    return 0;
}