3119번: OGRADA

https://www.acmicpc.net/problem/3119

높이가 h 이상인 나무판에 대해 남는 여부를 결정했다면 해당 나무판들은 최종적으로 남아있을 수 있다.
높이가 h 미만인 나무판들로 어떠한 울타리를 만들어도 높이가 h 이상인 나무판을 포함할 수 없기 때문이다.

그러므로 다음의 그리디 알고리즘이 가능하다.
1. 현재 남아있을지 결정해야 하는 나무판들의 높이 중 최댓값을 h라 한다.
2. 높이가 h인 나무판들에 대해 이미 남아 있기로 결정된 h보다 큰 나무판과 겹치는 부분을 제거한다. 높이가 h인 각 나무판마다 제거되지 않은 부분의 x 성분 최솟값을 si, 최댓값을 ei 라 하자.
3. i < j일 때 si < sj & ei < ej를 만족하도록 높이가 h인 나무판들을 최대한 많이 선별한다.
4. 선별된 나무판들을 최종적으로 남도록 결정한다.
5. 결정하지 못한 나무판들에 대해 1로 돌아가 처리한다.

2, 3번 과정은 map으로 처리 가능하다. 자세한 구현은 아래 소스를 참고하자.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int n;
struct st { int x, w, h, idx; }a[100000];
vector<int> res;
vector<pair<int, int> > stk;
map<int, int> mp;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].h), a[i].idx = i + 1;
    sort(a, a + n, [](st i, st j) {return i.h > j.h || i.h == j.h&&i.x < j.x; });
    for (int i = 0, s, e; i < n; i++) {
        auto it = mp.upper_bound(s = a[i].x);
        if (it != mp.begin() && s < (--it)->second) s = it->second;
        it = mp.upper_bound(e = a[i].x + a[i].w);
        if (it != mp.begin() && e <= (--it)->second) e = it->first;
        if (s < e && (stk.empty() || stk.back().second < e)) {
            while (!stk.empty() && stk.back().first == s) stk.pop_back(), res.pop_back();
            stk.push_back({ s,e });
            res.push_back(a[i].idx);
        }
        if (i == n - 1 || a[i].h^a[i + 1].h) {
            while (!stk.empty()) {
                s = stk.back().first;
                e = stk.back().second;
                it = mp.upper_bound(s);
                if (it != mp.begin() && s == prev(it, 1)->second) s = (--it)->first;
                while (it != mp.end() && it->first <= e) {
                    e = max(e, it->second);
                    mp.erase(it++);
                }
                mp[s] = e;
                stk.pop_back();
            }
        }
    }
    printf("%d\n", res.size());
    for (auto it : res) printf("%d ", it);
    return 0;
}

4004번: 쿠나이

https://www.acmicpc.net/problem/4004

풀이는 아래 링크로 대체한다.
https://algospot.com/wiki/old/232/APIO2012

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define idx(u,v) (gd[(u)/2][0]*x[v]+gd[(u)/2][1]*y[v])
#define pos(u) (2*x[u]-y[u])
#define dis(u,v) (abs(x[u]-x[v])+abs(y[u]-y[v]))
const int MXN = 1e5, dx[] = { 0,-1,0,1 }, dy[] = { 1,0,-1,0 }, fd[][3] = { { 0,7,11 },{ 1,3,9 },{ 2,5,10 },{ 4,6,8 } }, gd[][2] = { { 1,-1 },{ 1,1 },{ 1,-1 },{ 1,1 },{ 0,1 },{ 1,0 } };
map<int, map<int, int> > mc[12];
priority_queue<pair<int, pair<int, int> > > pq;
int x[MXN], y[MXN], d[MXN], w, h, n, ev[MXN], lt[MXN * 8], ct[MXN * 8];
long long res;
struct st { int l, r, p, c; };
vector<st> line;
vector<int> cd;
int find(int u, int v) {
    auto &mp = mc[u ^ 1][idx(u, v)];
    auto it = mp.upper_bound(pos(v));
    if (u & 1) {
        if (it == mp.begin()) return -1;
        return (--it)->second;
    }
    return it == mp.end() ? -1 : it->second;
}
void add(int t, int i) {
    if (!~i || t == ev[i]) return;
    ev[i] = t;
    int sx = x[i], sy = y[i], ex = sx + t / 2 * dx[d[i]], ey = sy + t / 2 * dy[d[i]];
    if (sx > ex) swap(sx, ex);
    if (sy > ey) swap(sy, ey);
    sx = max(sx, 1);
    sy = max(sy, 1);
    ex = min(ex, h) + 1;
    ey = min(ey, w) + 1;
    line.push_back({ sx,ex,sy,1 });
    line.push_back({ sx,ex,ey,-1 });
    cd.push_back(sx);
    cd.push_back(ex);
    for (int it : fd[d[i]]) {
        int h = find(it, i), t;
        if (~h) {
            mc[it][idx(it, i)].erase(pos(i));
            t = find(it ^ 1, h);
            if (~t) pq.push({ -dis(h, t), make_pair(h, t) });
        }
    }
}
void update(int h, int l, int r, int gl, int gr, int c) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) ct[h] += c;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, c);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, c);
    }
    lt[h] = ct[h] ? cd[r + 1] - cd[l] : l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0;
}
int main() {
    scanf("%d%d%d", &w, &h, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", y + i, x + i, d + i);
        pq.push({ -2e9, make_pair(i,-1) });
        ev[i] = 2e9 + 1;
    }
    for (int i = 0; i < n; i++) for (int it : fd[d[i]]) {
        int t = find(it, i);
        if (~t) pq.push({ -dis(i,t), make_pair(i,t) });
        mc[it][idx(it, i)][pos(i)] = i;
    }
    while (!pq.empty()) {
        int t = -pq.top().first;
        pair<int, int> p = pq.top().second;
        pq.pop();
        if (ev[p.first] < t || ~p.second && ev[p.second] < t) continue;
        add(t, p.first);
        add(t, p.second);
    }
    sort(cd.begin(), cd.end());
    cd.erase(unique(cd.begin(), cd.end()), cd.end());
    sort(line.begin(), line.end(), [](st u, st v) {return u.p < v.p; });
    for (int i = 0; i < line.size(); i++) {
        if (i) res += 1LL * (line[i].p - line[i - 1].p)*lt[0];
        update(0, 0, cd.size() - 1, lower_bound(cd.begin(), cd.end(), line[i].l) - cd.begin(),
            lower_bound(cd.begin(), cd.end(), line[i].r) - cd.begin() - 1, line[i].c);
    }
    printf("%lld", res);
    return 0;
}

2957번: BST

https://www.acmicpc.net/problem/2957

$O(n\lg n)$

a[0...n-1]에 입력받은 순서대로 정수가 저장되어 있다고 하자.
a[i]는 a[0...i-1]를 가지고 만든 이진 탐색 트리에 추가하게 된다.
a[0...i-1] 중 a[i]보다 작은 최댓값, 큰 최솟값을 가진 노드를 각각 p, q라고 놓자.
만약 그러한 노드가 없다면 해당 p 혹은 q는 더미 노드로써 레벨이 -1이라고 생각하자.

다음 두 가지 경우가 가능하다.
i) p의 레벨 < q의 레벨
q의 왼편에 x를 추가하게 됨
ii) p의 레벨 > q의 레벨
p의 오른편에 x를 추가하게 됨

따라서 a[i]의 레벨은 max(p의 레벨, q의 레벨) + 1 이다.
map을 통해 (key = a[i], value = a[i]의 레벨)들을 관리하면 매 입력마다 이진 검색을 적절히 활용하여 위 과정을 수행할 수 있다.

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int n, x, t;
long long s;
map<int, int> mp = { { 0,-1 },{ 300001,-1 } };
int main() {
    for (scanf("%d", &n); n--;) {
        scanf("%d", &x);
        auto it = mp.upper_bound(x);
        t = it--->second;
        s += mp[x] = max(it->second, t) + 1;
        printf("%lld\n", s);
    }
    return 0;
}

$O(n)$

입력을 모두 받아 트리를 완성하고 반대로 노드를 하나씩 삭제한다.
이렇게 하면 map을 사용하지 않고 간단한 합집합 연산으로 각 시점의 (위에서 언급한)p, q를 구할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 3e5;
int n, l[MXN + 2], r[MXN + 2], a[MXN + 1], p[MXN + 1], q[MXN + 1], lev[MXN + 2];
long long res;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        l[i] = i - 1;
        r[i] = i + 1;
    }
    for (int i = n; i; i--) {
        p[a[i]] = l[a[i]];
        q[a[i]] = r[a[i]];
        r[l[a[i]]] = r[a[i]];
        l[r[a[i]]] = l[a[i]];
    }
    lev[0] = lev[n + 1] = -1;
    for (int i = 1; i <= n; i++) {
        res += lev[a[i]] = max(lev[l[a[i]]], lev[r[a[i]]]) + 1;
        printf("%lld\n", res);
    }
    return 0;
}

6231번: Gold Balanced Lineup

https://www.acmicpc.net/problem/6231


$O(kn\lg n)$

sum(a[0][i...j]) = sum(a[1][i...j]) = ... = sum(a[k-1][i...j])인 최대 j-i+1을 구하는 문제

s[i][j]=sum(s[i][1...j])라고 하면
s[0][j]-s[0][i-1] = s[1][j]-s[1][i-1] = ... = s[k-1][j]-s[i-1][i-1]
이와 동치인 연립등식은 다음과 같다.
s[0][j]-s[k-1][j] = s[0][i-1]-s[k-1][i-1]
s[1][j]-s[k-1][j] = s[1][i-1]-s[k-1][i-1]
...
s[k-2][j]-s[k-1][j] = s[k-2][i-1]-s[k-1][i-1]

이제 (s[0...k-2][i]-s[k-1][i])가 key인 해쉬를 이용하면 매 i마다 같은 key값의 최소 인덱스를 빠르게 구할 수 있다.

#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int n, k, r;
map<vector<int>, int> mp;
int main() {
    scanf("%d%d", &n, &k);
    vector<int> s(k);
    mp[s] = 0;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        for (int j = k; j--; x /= 2) s[j] += x & 1;
        for (auto &it : s) it -= s[k - 1];
        auto it = mp.find(s);
        if (it != mp.end()) r = max(r, i - it->second);
        else mp[s] = i;
    }
    printf("%d", r);
    return 0;
}

4012번: 컨벤션 센터

https://www.acmicpc.net/problem/4012


$O(n\lg n)$

개구간 (l,r)에 컨벤션 센터를 이용할 수 있는 단체의 최대 개수 f(l,r)을 빠르게 구할 수 있다고 해보자.
그럼 1번 단체부터 차례대로 스케줄에 넣어 보면서 최적해를 유지하는지 빠르게 판단할 수 있다.
(스케줄 상 두 단체 사이 구간을 파악하는 일련의 연산은 map, set을 활용하여 해결할 수 있다.)

<f(l,r) 구하는 방법>
먼저, 단체를 회의 시작시간을 기준으로 오름차순 정렬하자.
x번 단체 바로 앞에 회의가 진행되었을 경우, 그 단체는 x번 단체 회의 시작 이전에 회의가 끝난 단체 중 시작 시간이 가장 늦은 단체여야 유리하다.
이러한 성질을 이용하여
dp[x][i]: x번 단체의 2^i번째 이전 단체
인 sparse table을 만들 수 있다.
그럼 r 전에 끝난 단체 중 가장 늦게 시작한 단체 p를 찾은 뒤
p의 2^i 이전 단체가 l 이후에 시작했는지 여부에 따라 p를 옮겨가며 카운트 하면 f(l,r)을 $O(\lg n)$에 구할 수 있다.

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int MXN = 2e5;
int n, dp[MXN + 1][18], top = 1;
pair<int, int> stk[MXN + 1], p[MXN + 1], s[MXN + 1], e[MXN + 1];
int f(int l, int r) {
    int x = (lower_bound(stk, stk + top, make_pair(r, 0)) - 1)->second, ret = 1;
    if (p[x].first <= l) return 0;
    for (int i = 17; i >= 0; i--) if (p[dp[x][i]].first > l) x = dp[x][i], ret += 1 << i;
    return ret;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].first, &p[i].second);
        s[i] = { p[i].first,i };
        e[i] = { p[i].second,i };
    }
    sort(s + 1, s + 1 + n);
    sort(e + 1, e + 1 + n);
    for (int i = 1, j = 1, prv = 0; i <= n; i++) {
        for (; e[j].first < s[i].first; j++) if (p[prv].first < p[e[j].second].first) prv = e[j].second;
        while (stk[top - 1].first >= p[s[i].second].second) top--;
        stk[top++] = { p[s[i].second].second,s[i].second };
        dp[s[i].second][0] = prv;
        for (int j = 1; j < 18; j++) dp[s[i].second][j] = dp[dp[s[i].second][j - 1]][j - 1];
    }
    printf("%d\n", f(0, 2e9));
    map<int, int> mp;
    mp[0] = 0;
    mp[2e9] = 2e9;
    for (int i = 1; i <= n; i++) {
        auto l = mp.lower_bound(p[i].first), r = l--;
        if (l->second < p[i].first&&p[i].second < r->first
            &&f(l->second, r->first) == f(l->second, p[i].first) + 1 + f(p[i].second, r->first)) {
            printf("%d ", i);
            mp[p[i].first] = p[i].second;
        }
    }
    return 0;
}

2358번: 평행선

https://www.acmicpc.net/problem/2358


$O(n\lg n)$

x, y 좌표값이 같은 점이 두 개 이상 있는 경우를 센다.

#include<cstdio>
#include<map>
using namespace std;
map<int, int> x, y;
int n, u, v, r;
int main() {
    for (scanf("%d", &n); n--;) {
        scanf("%d%d", &u, &v);
        r += (++x[u] == 2) + (++y[v] == 2);
    }
    printf("%d", r);
    return 0;
}

2015번: 수들의 합 4

https://www.acmicpc.net/problem/2015



$O(n\lg n)$

s[i]: 1...i 번째 수들의 합
s[i]-s[j]=k(j<i)인 i,j를 찾아야 하므로
모든 X=s[j]인 j(j<i)의 개수를 구해놓으면 해결할 수 있다.

#include<cstdio>
#include<map>
using namespace std;
int s, x, n, k;
map<int, int> mp;
long long r;
int main() {
    mp[0]++;
    for (scanf("%d%d", &n, &k); n--;) {
        scanf("%d", &x);
        s += x;
        r += mp[s - k];
        mp[s]++;
    }
    printf("%lld", r);
    return 0;
}

10816번: 숫자 카드 2

https://www.acmicpc.net/problem/10816


$O(n+m)$

#include<cstdio>
#define s (int)1e7
int n, a[2 * s + 1], x;
int main() {
    for (scanf("%d", &n); n--;) scanf("%d", &x), a[x + s]++;
    for (scanf("%d", &n); n--;) scanf("%d", &x), printf("%d ", a[x + s]);
    return 0;
}

$O((n+m)\lg n)$

#include<cstdio>
#include<map>
using namespace std;
map<int, int> mp;
int n, x;
int main() {
    for (scanf("%d", &n); n--;) scanf("%d", &x), mp[x]++;
    for (scanf("%d", &n); n--;) scanf("%d", &x), printf("%d ", mp[x]);
    return 0;
}

$O((n+m)\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[500000], x;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    for (scanf("%d", &m); m--;) {
        scanf("%d", &x);
        printf("%d ", upper_bound(a, a + n, x) - lower_bound(a, a + n, x));
    }
    return 0;
}

7662번: 이중 우선순위 큐

https://www.acmicpc.net/problem/7662


$O(tklgk)$

multiset을 쓴다.

#include<cstdio>
#include<set>
using namespace std;
int t, k, x;
char c;
int main() {
    for (scanf("%d", &t); t--;) {
        multiset<int> ms;
        for (scanf("%d", &k); k--;) {
            scanf(" %c%d", &c, &x);
            if (c == 'I') ms.insert(x);
            else if (!ms.empty()) x < 0 ? ms.erase(ms.begin()) : ms.erase(--ms.end());
        }
        ms.empty() ? puts("EMPTY") : printf("%d %d\n", *ms.rbegin(), *ms.begin());
    }
    return 0;
}

11813번: GALAKSIJA

https://www.acmicpc.net/problem/11813


$O(n{\lg n}^2)$

w[i]: 1~i 경로상 가중치를 xor 한 것
p~q 경로상 가중치를 xor 한 것과 w[p]^w[q]이 같다.
고로 문제는 w[i]가 같은 쌍의 개수를 구하는 문제가 된다.
이는 map과 유니온 파인드 자료구조를 이용하면 위 시간복잡도에 해결할 수 있다.

간선을 삭제하는 쿼리들을 모두 받아놓은 뒤 반대로 나중 명령부터 처리하여 합집합하는 쿼리로 바꿔보자.
각 집합에 있는 w값 종류 수(집합의 크기)가 작은 쪽에서 큰 쪽으로 원소를 옮기며 합친다.
이 때 집합간 존재하는 w가 같은 쌍의 개수를 누적해준다.
합치는 명령은 총 O(nlgn)번 일어나며 각 원소를 합치는 연산이 O(lgn)이므로 위 시간복잡도가 나온다.

#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int MXN = 1e5;
int n, e[MXN][3], q[MXN + 1], w[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
long long r[MXN + 1], s;
struct st {
    int p[MXN + 1];
    map<int, int> mp[MXN + 1];
    void init() { for (int i = 1; i <= n; i++) p[i] = i, mp[i][w[i]]++; }
    int rt(int x) { return x^p[x] ? p[x] = rt(p[x]) : x; }
    void un(int x, int y) {
        int rx = rt(x), ry = rt(y);
        if (mp[rx].size() < mp[ry].size()) swap(rx, ry);
        for (auto it : mp[ry]) {
            s += (long long)mp[rx][it.first] * it.second;
            mp[rx][it.first] += it.second;
        }
        p[ry] = rx;
    }
}uf;
void dfs(int h, int p) {
    for (auto it : adj[h]) if (it.first^p) w[it.first] = w[h] ^ it.second, dfs(it.first, h);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i<n; i++) {
        scanf("%d%d%d", e[i], e[i] + 1, e[i] + 2);
        adj[e[i][0]].push_back({ e[i][1],e[i][2] });
        adj[e[i][1]].push_back({ e[i][0],e[i][2] });
    }
    for (int i = 1; i < n; i++) scanf("%d", q + i);
    dfs(1, 0);
    uf.init();
    for (int i = n; --i;) uf.un(e[q[i]][0], e[q[i]][1]), r[i] = s;
    for (int i = 1; i <= n; i++) printf("%lld\n", r[i]);
    return 0;
}

2261번: 가장 가까운 두 점

https://www.acmicpc.net/problem/2261

#include<stdio.h>
#include<algorithm>
#include<set>
#define x first
#define y second
using namespace std;
pair<int, int> p[100000];
set<pair<int, int> > st;
int n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    sort(p, p + n);
    int res = 1e9, rt = sqrt(res);
    for (int i = 0, h = 0; i < n; i++) {
        while (p[i].x - p[h].x>rt) st.erase({ p[h].y, p[h++].x });
        for (set<pair<int, int> >::iterator it = st.lower_bound({ p[i].y - rt, -1e9 });
        it != st.end() && it->x <= p[i].y + rt; it++) {
            int d = (p[i].x - it->y)*(p[i].x - it->y) + (p[i].y - it->x)*(p[i].y - it->x);
            if (d < res) {
                res = d;
                rt = sqrt(d);
            }
        }
        st.insert({ p[i].y, p[i].x });
    }
    printf("%d", res);
    return 0;
}