푸키키키 :: 푸키키키

#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);
        vector<int> input2(n + 1);
        for (int i = 1; i <= n; ++i) {
               cin >> input[i];
               input2[i] = -input[i];
        }
        RMQ myRMQ(input);
        RMQ myRMQ2(input2);
        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) << ' ' << -myRMQ2.query(a,b) << '\n';
        }
        return 0;
}

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

큰 정수를 순서대로 사용하고 싶으면 map으로 300 -> 0 번 index 이렇게 할 수 있다.
하는 방법은

arr[0] = 300;
map<int,int> myMap;
myMap[300] = 0;

...

int arridx = myMap[300];
cout << arr[arridx];

BIT에서 구간합 구하는 핵심 코드

myTree.sum(n) - myTree.sum(idxB);

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
//펜윅 트리의 구현, 가상의 배열 A[]의 부분합을
//빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의
//원소가 전부 0이라고 생각한다.
typedef long long ll;
struct FenwickTree {
        vector<ll> tree;
        FenwickTree(ll n) : tree(n + 1) {}
        ll sum(ll pos) {
               ++pos;
               ll ret = 0;
               while (pos > 0) {
                       ret += tree[pos];
                       pos &= (pos - 1);
               }
               return ret;
        }
        void add(ll pos, ll val) {
               ++pos;
               while (pos < tree.size()) {
                       tree[pos] += val;
                       pos += (pos & -pos);
               }
        }
};
int main(void) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        ll n, m, k;
        cin >> n;
        vector<ll> arr1(n);
        map<ll, ll> B;
        for (int i = 0; i < n; ++i) {
               cin >> arr1[i];
        }
        ll temp;
        for (int i = 0; i < n; ++i) {
               cin >> temp;
               B[temp] = i;
        }
        FenwickTree myTree(1000001);
        ll cnt = 0;
        for (int i = 0; i < n; ++i) {
               int valA = arr1[i];
               int idxB = B[valA];
               cnt += myTree.sum(n) - myTree.sum(idxB);
               myTree.add(idxB, 1);
        }
        cout << cnt << endl;
        
        return 0;
}

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

//백준 1005

// 만들어야 하는 건물 에서 dfs 해서 제일 시간 오래 걸리는 곳 까지 탐색

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

int fb;//final building

int bt[1010]; //build time

//vector<int> adj[1010];

vector<int> jda[1010];

int dp[1010];

bool ch_fb = false;

bool visited[1001];

vector<int> order;

int dfs(int x) {

if (jda[x].size() == 0) {

return bt[x];

}

int& ret = dp[x];

if (ret != -1) {

return ret;

}

ret = 0;

int N_idx;

for (N_idx = 0; N_idx < jda[x].size(); ++N_idx) {

ret = max(dfs(jda[x][N_idx]) + bt[x], ret);

}

return ret;

}

//위상정렬 포기

//void ddfs(int x) {

// visited[x] = true;

// int temp;

// for (int next = 0; next < adj[x].size(); ++next) {

// temp = adj[x][next];

// if (visited[temp] == false) {

// dfs(temp);

// }

// order.push_back(temp);

//}

//int a, b;

//void topologicalSort() {

// int n = a;

// memset(visited, false, sizeof(visited));

// order.clear();

// for (int i = 1; i <= n; ++i) {

// if (!visited[i]) {

// dfs(i);

// }

// reverse(order.begin(), order.end());

// return ;

//}

int main(void)

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int k1, k2;//for input

int t;

cin >> t;

while (t--) {

for (int i = 0; i < 1010; ++i) {

jda[i].clear();

}

memset(dp, -1, sizeof(dp));

memset(bt, -1, sizeof(bt));

int a, b;

cin >> a >> b;

for (int i = 1; i <= a; ++i) {

cin >> bt[i];

}

for (int i = 0; i < b; ++i) {

cin >> k1 >> k2;

//adj[k1].push_back(k2);

jda[k2].push_back(k1);

}

cin >> fb;

cout << dfs(fb) << '\n';

//for (int i = 1; i <= a; ++i) {

// cout << dp[i] << ' ';

//}

//cout << "끝" << endl; /*debugging*/

}

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

푸키키키

전체 글

[세그먼트트리] 백준 2357 최소값과 최대값

[BIT] 백준 7578 공장 (map활용)

[DFS] 백준 1005 ACM-Craft

+ Recent posts

티스토리툴바