YEZAELP

SMMR-246: Median (Segment Tree)

Jun 13th, 2021 (edited)
474
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5. const int N = 2e5;
  6. int tree[1 << 19];
  7. int pst[N+10], ar[N+10];
  8. unordered_map <int, int> num; // num[number] -> position
  9. int n;
  10.  
  11. void update(int idx, int l, int r, int upd){
  12.     if(l == r) {
  13.         tree[idx] = 1;
  14.         return;
  15.     }
  16.     int mid = (l + r) / 2;
  17.     if(upd <= mid) update(2*idx, l, mid, upd);
  18.     else update(2*idx+1, mid+1, r, upd);
  19.     tree[idx] = tree[2*idx] + tree[2*idx+1];
  20. }
  21.  
  22. void update_tree(int x){
  23.     update(1, 1, n, num[x]);
  24.     num[x] ++;
  25. }
  26.  
  27. int query1(int x){
  28.     int l = 1, r = n, idx = 1;
  29.     while(l != r){
  30.         int mid = (l + r) / 2;
  31.         if(x > tree[2*idx]){
  32.             x -= tree[2*idx];
  33.             idx = 2 * idx + 1;
  34.             l = mid + 1;
  35.         }
  36.         else {
  37.             idx = 2 * idx;
  38.             r = mid;
  39.         }
  40.     }
  41.     return r;
  42. }
  43.  
  44. int query2(int x){
  45.     int l = 1, r = n, idx = 1;
  46.     while(l != r){
  47.         int mid = (l + r) / 2;
  48.         if(x > tree[2*idx+1]){
  49.             x -= tree[2*idx+1];
  50.             idx = 2 * idx;
  51.             r = mid;
  52.         }
  53.         else {
  54.             idx = 2 * idx + 1;
  55.             l = mid + 1;
  56.         }
  57.     }
  58.     return l;
  59. }
  60.  
  61. int main(){
  62.  
  63.     scanf("%d", &n);
  64.  
  65.     for(int i=1;i<=n;i++) {
  66.         scanf("%d", &ar[i]);
  67.         pst[i] = ar[i];
  68.     }
  69.  
  70.     sort(pst + 1, pst + n + 1);
  71.  
  72.     for(int i=1;i<=n;i++){
  73.         if(num[ pst[i] ] == 0) num[pst[i]] = i;
  74.     }
  75.  
  76.     for(int i=1;i<=n;i++){
  77.         update_tree(ar[i]);
  78.         if(i % 2 == 1) {
  79.             int x = i/2 + 1;
  80.             printf("%d ", pst[ query1(x) ]);
  81.         }
  82.         else {
  83.             int x = i/2;
  84.             printf("%d ", (pst[ query1(x) ] + pst[ query2(x) ]) / 2);
  85.         }
  86.     }
  87.  
  88.     return 0;
  89. }
  90.  
RAW Paste Data