//절대값이 같은 음수, 양수가 있으면 음수가 더 위에 있어야 한다.
#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <algorithm>
#define abs(a) (a>0 ? a : -a)
using namespace std;
vector<int> heap;
void push_heap(vector<int>& heap, int newValue) {
        heap.push_back(newValue);
        int idx = heap.size() - 1;
        while (idx > 0 && (abs(heap[(idx - 1) / 2]) > abs(heap[idx]) || ((abs(heap[(idx - 1) / 2]) == abs(heap[idx]) && heap[(idx - 1) / 2] > heap[idx])))) {
               swap(heap[idx], heap[(idx - 1) / 2]);
               idx = ((idx - 1) / 2);
        }
}
void pop_heap(vector<int>& heap) {
        heap[0] = heap.back();
        heap.pop_back();
        int here = 0;
        while (true) {
               int left = here * 2 + 1, right = here * 2 + 2;
               if (left >= heap.size()) {
                       break;
               }
               int next = here;
               if (abs(heap[next]) > abs(heap[left])) {
                       next = left;
               }
               else if (abs(heap[next]) == abs(heap[left]) && heap[next] > heap[left]) {
                       next = left;
               }
               if (right < heap.size() && abs(heap[next]) > abs(heap[right]))
                       next = right;
               else if (right < heap.size() && abs(heap[next]) == abs(heap[right]) && heap[next] > heap[right]) {
                       next = right;
               }
               if (next == here)
                       break;
               swap(heap[here], heap[next]);
               here = next;
        }
        
}
int main(void) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
               int k;
               cin >> k;
               if(k!=0)
                       push_heap(heap,k);
               else {
                       if (!heap.empty()) {
                               cout << heap[0] << endl;
                               pop_heap(heap);
                       }
                       else {
                               cout << 0 << endl;
                       }
               }
        }
        
        return 0;
}

저작자표시 비영리 변경금지

//절대값이 같은 음수, 양수가 있으면 음수가 더 위에 있어야 한다.
#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <algorithm>
#define abs(a) (a>0 ? a : -a)
using namespace std;
int main(void) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        priority_queue<int, vector<int>,greater<int>> minh;
        priority_queue<int, vector<int>,less<int>> maxh;
        int n,input;
        cin >> n;
        for (int i = 0; i < n; ++i) {
               cin >> input;
               if (minh.size() == maxh.size()) {
                       maxh.push(input);
               }
               else {
                       minh.push(input);
               }
               if (!maxh.empty() && !minh.empty() && maxh.top() > minh.top()) {
                       int a = maxh.top();
                       int b = minh.top();
                       maxh.pop();
                       minh.pop();
                       maxh.push(b);
                       minh.push(a);
               }
               cout << maxh.top() << '\n';
        }
        return 0;
}

저작자표시 비영리 변경금지
  • init 만 보면 된다.
  • 받는 배열의 index는 1부터 시작한다.
  • 여기서 init안의 left는 0부터 시작하므로 받는 배열의 0번에는 0이 저장되어 있는데 init 함수가 재귀로 돌면서 이 값까지 처리한다. 
  • query로 찾을 때 답에는 영향이 없는데 최상위 노드에는 0이 저장된다. 
  • 이경우 left를 1로 바꾸면 최상위 노드가 5가된다. 

  • segment트리는 힙처럼 왼쪽 맨 아래부터 채워지는 게 아니라 다른 방식으로 채워진다. 





#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
using namespace std;
struct RMQ {
        int n;
        vector<int> rangeMin;
        RMQ(const vector<int>& arr) {
               n = arr.size();
               rangeMin.resize(4 * n);
               init(arr, 0, n - 1, 1);
        }
        int init(const vector<int>& arr, int left, int right, int node) {
               if (left == right) {
                       return rangeMin[node] = arr[left];
               }
               int mid = (left + right) / 2;
               int leftMin = init(arr, left, mid, 2 * node);
               int rightMin = init(arr, mid + 1, right, 2 * node + 1);
               return rangeMin[node] = min(leftMin, rightMin);
        }
        int query(int left, int right, int node, int nodeLeft, int nodeRight) {
               if (right < nodeLeft || left > nodeRight) {
                       return INT32_MAX;
               }
               if (left <= nodeLeft && right >= nodeRight) {
                       return rangeMin[node];
               }
               int mid = (nodeLeft + nodeRight) / 2;
               int leftbaby = query(left, right, node * 2, nodeLeft, mid);
               int rightbaby = query(left, right, node * 2 + 1, mid + 1, nodeRight);
               return min(leftbaby, rightbaby);
        }
        int query(int left, int right) {
               return query(left, right, 1, 0, n - 1);
        }
        int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
               //index가 범위와 관계없을 경우
               if (index < nodeLeft || index > nodeRight) {
                       return rangeMin[node];
               }
               //리프까지 내려온 경우
               if (nodeLeft == nodeRight) {
                       return rangeMin[node] = newValue;
               }
               int mid = (nodeLeft + nodeRight) / 2;
               int a = update(index, newValue, 2 * node, nodeLeft, mid);
               int b = update(index, newValue, 2 * node + 1, mid + 1, nodeRight);
               return rangeMin[node] = min(a, b);
        }
        int update(int index, int newValue) {
               return update(index, newValue, 1, 0, n - 1);
        }
};
int main(void) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int n, m;
        cin >> n >> m;
        vector<int> input(n+1);
        for (int i = 1; i <= n; ++i) {
               cin >> input[i];
        }
        RMQ myRMQ(input);
        int cnt = 1;
        int first_2 = 2;
        //for (int i = 1; i < myRMQ.rangeMin.size(); ++i) {
        //      
        //      cout << myRMQ.rangeMin[i] << ' ';
        //      cnt++;
        //      if (cnt == first_2) {
        //             cout << endl;
        //             first_2 *= 2;
        //      }
        //}
        int a, b;
        
        for (int i = 0; i < m; ++i) {
               cin >> a >> b;
               cout << myRMQ.query(a, b) << '\n';
        }
        return 0;
}


저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바