首页 > 代码库 > poj2104 划分树 区间K大 在线 无修改

poj2104 划分树 区间K大 在线 无修改

2024-07-15 14:54:24   223人阅读

博主sbit。。。。对于高级数据结构深感无力，然后这些东西在OI竟然烂大街了，不搞就整个人都不好了呢。

于是我勇猛的跳进了这个大坑

　　　　　　　　　　——sbit

区间K大的裸题，在线，无修改。

可以用归并树（\(O(nlog^3n)\)），也可用划分树（\(O(nlogn + mlogn)\)）。果断划分树。。。（以后再来看归并树。。。再来看。。。来看。。看。。）

划分树是个什么东西呢？为什么可以做区间k大呢？

想想平衡树做k大时是如何搞的，其实内在原理是一样的。

划分树分两个步骤：建树与询问，这两个步骤相互关联，互相影响。

待update （其实sbit还没完全理解查询）

 

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 100000 + 10; 5 int val[20][maxn], sorted[maxn], to_left[20][maxn]; 6 int n, m; 7 void build_tree(int l, int r, int layer) { 8     if(l == r) return ; 9     int mid = (l + r) >> 1;10     int suppose = mid - l + 1;11     for(int i = l; i <= r; ++i)12         if(val[layer][i] < sorted[mid])13             --suppose;14     int rec_l = l, rec_r = mid + 1;15     for(int i = l; i <= r; ++i) {16         if(i == l) {17             to_left[layer][i] = 0;18         } else {19             to_left[layer][i] = to_left[layer][i - 1];20         }21         if(val[layer][i] < sorted[mid]) {22             ++to_left[layer][i];23             val[layer + 1][rec_l++] = val[layer][i];24         } else if(val[layer][i] > sorted[mid]) {25             val[layer + 1][rec_r++] = val[layer][i];26         } else {27             if(suppose != 0) {28                 --suppose;29                 ++to_left[layer][i];30                 val[layer + 1][rec_l++] = val[layer][i];31             } else {32                 val[layer + 1][rec_r++] = val[layer][i];33             }34         }35     }36     build_tree(l, mid, layer + 1);37     build_tree(mid + 1, r, layer + 1);38 }39 40 int query(int l, int r, int layer, int ql, int qr, int kth) {41     if(l == r) return val[layer][l];42     int s, ss;43     if(l == ql) {44         s = 0;45         ss = to_left[layer][qr];46     } else {47         s = to_left[layer][ql - 1];48         ss = to_left[layer][qr] - s;49     }50     int mid = (l + r) >> 1;51     if(kth <= ss) {52         return query(l, mid, layer + 1, l + s, l + s + ss - 1, kth);53     }54     return query(mid + 1, r, layer + 1, mid + 1 + ql - s - l, mid + 1 + qr - l - s - ss, kth - ss);55 }56 57 int main() {58 #ifndef ONLINE_JUDGE59     freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);60 #endif61     scanf("%d%d", &n, &m);62     for(int i = 1; i <= n; ++i) {63         scanf("%d", &sorted[i]);64         val[0][i] = sorted[i];65     }66     sort(sorted + 1, sorted + n + 1);67     build_tree(1, n, 0);68     while(m--) {69         int l, r, k;70         scanf("%d%d%d", &l, &r, &k);71         printf("%d\n", query(1, n, 0, l, r, k));72     }73     return 0;74 }
View Code

 


联系
我们