首页 > 代码库 > hdoj 2665 Kth number主席树裸

hdoj 2665 Kth number主席树裸

2024-08-15 19:49:10   210人阅读

Kth number

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9417    Accepted Submission(s): 2938

Problem Description
Give you a sequence and ask you the kth big number of a inteval.
 
Input
The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]
 
Output
For each test case, output m lines. Each line contains the kth big number.
 
Sample Input
1 10 1 1 4 2 3 5 6 7 8 9 0 1 3 2
 
Sample Output
2
裸的主席树。copy下模板
 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5  6 const int M = 1000008; 7  8 struct Node{ 9     int r, l, sum;10 }T[M*20];11 struct A{12     int idx, x;13     bool operator <(const A & o)const{14         return x < o.x;15     }16 }a[M];17 int T_cnt;18 void inser(int &num, int &x, int L, int R){19     T[T_cnt++] = T[x]; x = T_cnt-1;20     ++T[x].sum;21     if(L == R) return;22     int mid = (L+R)>>1;23     if(num <= mid) inser(num, T[x].l, L, mid);24     else inser(num, T[x].r, mid+1, R);25 }26 int query(int i, int j, int k, int L, int R){27     if(L == R) return L;28     int t = T[T[j].l].sum - T[T[i].l].sum;29     int mid = (R+L)>>1;30     if(k <= t) return query(T[i].l, T[j].l, k, L, mid);31     else return query(T[i].r, T[j].r, k-t, mid+1, R);32 }33 int ranks[M], root[M];34 int n, m, t;35 int main(){36     T[0].r = T[0].r = T[0].sum = 0;37     root[0] = 0;38     scanf("%d", &t);39     while(t--){40         scanf("%d%d", &n, &m);41         for(int i = 1; i <= n; i++) {42             scanf("%d", &a[i].x);43             a[i].idx = i;44         }45         sort(a+1, a+n+1);46         for(int i = 1; i <= n; i++){47             ranks[a[i].idx] = i;48         }49         T_cnt = 1;50         for(int i = 1; i <= n; i++){51             root[i] = root[i-1];52             inser(ranks[i], root[i], 1, n);53         }54         while(m--){55             int i, j, k;56             scanf("%d%d%d", &i, &j, &k);57             printf("%d\n", a[query(root[i-1], root[j], k, 1, n)].x);58         }59     }60 }

 

hdoj 2665 Kth number主席树裸


联系
我们