7795번: 먹을 것인가 먹힐 것인가

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


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

a[i]>b[j]인 (i,j) 쌍을 구하는 문제
a[0...n-1]을 오름차순 정렬한 다음,
각 j마다 b[j]보다 크면서 가장 작은 a[i]의 i를 p라고 할 때 n-p를 누적해준다.

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

14181번: 함수와 쿼리

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

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

f(x,y)를 쉽게 생각해보자.
a[y]
a[y] a[y-1]
a[y] a[y-1] a[y-2]
...
a[y] a[y-1] a[y-2] ... a[y-x+2] a[y-x+1]
이런 삼각형 모양의 배열의 맨 위에 포인터 p가 있다하자.
p는 바로 아래 혹은 아래 오른쪽으로 움직인다.
맨 위에서 아래까지 움직일 때 p가 지나간 항들 합의 최소가 f(x,y)이다.

편의상 t=y-x+1, s[i]=a[1]+a[2]+...+a[i]라 하자.
잘 생각해보면 대각선으로만 움직이다 아래로만 내려가는 경로 중에 최적루트가 있다.
이때, 도착지점이 a[i]라 하면 a[i+1...y]>a[i]이다. ... (*)
즉, f(x,y)=min(t<=i<=t)(s[y]-s[i]+a[i]*(i-t+1))
min 안을 정리해서 다시 쓰면
-a[i]*t+(i+1)*a[i]-s[i]+s[y]
(*)에 의해 [t,y]에 있고 -a[i]가 단조 감소인 i에 대해 (기울기, y절편)=(-a[i],(i+1)*a[i]-s[i]) 직선들을 생각할 수 있다.
이들을 이용해 최솟값을 이루는 convex hull을 만들어 x=t인 지점의 함수값을 구하면 f(x,y)를 구할 수 있다.

다수의 쿼리 빠르게 처리하기 위해 세그먼트 트리를 이용한다.
트리의 [l,r] 구간에 해당하는 convex hull을 미리 만들어 놓고 쿼리 (a,b)가 들어오면 이에 해당하는 구간들의 x=a에서 함수값 중 최솟값을 출력한다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
typedef pair<double, double> line;
int n, m, sz[MXN * 4], a[MXN + 1], s[MXN + 1];
vector<line> v[MXN * 4];
vector<double> x[MXN * 4];
double cross(line i, line j) { return (i.second - j.second) / (j.first - i.first); }
void add(int h, int l, int r, int g, line t) {
    if (r < g || g < l) return;
    if (l^r) {
        add(h * 2 + 1, l, (l + r) / 2, g, t);
        add(h * 2 + 2, (l + r) / 2 + 1, r, g, t);
    }
    v[h].resize(r - l + 1);
    x[h].resize(r - l + 1);
    while (sz[h] && v[h][sz[h] - 1].first <= t.first || sz[h] > 1 && cross(v[h][sz[h] - 2], t)>cross(v[h][sz[h] - 1], t)) sz[h]--;
    if (sz[h]) x[h][sz[h] - 1] = cross(v[h][sz[h] - 1], t);
    v[h][sz[h]++] = t;
}
int query(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 1e9;
    if (gl <= l&&r <= gr) {
        int p = lower_bound(x[h].begin(), x[h].begin() + sz[h] - 1, gl) - x[h].begin();
        return v[h][p].first*gl + v[h][p].second;
    }
    return min(query(h * 2 + 1, l, (l + r) / 2, gl, gr), query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        s[i] = s[i - 1] + a[i];
        add(0, 1, n, i, { -a[i],(i + 1)*a[i] - s[i] });
    }
    scanf("%d", &m);
    for (int i = 0, u, v; i < m; i++) {
        scanf("%d%d", &u, &v);
        printf("%d\n", query(0, 1, n, v - u + 1, v) + s[v]);
    }
    return 0;
}

1920번: 수 찾기

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


$O(n+m\lg n)$

이진 검색을 이용한다.

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

9007번: 카누 선수

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


$O(tn^2\lg n)$

두 반씩 합 쌍을 모두 구해놓고 정렬한 다음, 이분 검색을 통해 두 수열에서 k에 가까운 두 수의 합을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, a[4][1000], b[1000000], n, k;
int main() {
        for (scanf("%d", &t); t--;) {
                scanf("%d%d", &k, &n);
                int r = 1e9;
                for (int i = 0; i < 4; i++)
                    for (int j = 0; j < n; j++) scanf("%d", a[i] + j);
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++) b[i*n + j] = a[2][i] + a[3][j];
                sort(b, b + n*n);
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                                int s = a[0][i] + a[1][j], p = lower_bound(b, b + n*n, k - s) - b;
                                if (p<n*n && (abs(r - k)>abs(s + b[p] - k) || abs(r - k) == abs(s + b[p] - k) && r>s + b[p])) r = s + b[p];
                                if (p && (abs(r - k)>abs(s + b[p - 1] - k) || abs(r - k) == abs(s + b[p - 1] - k) && r>s + b[p - 1])) r = s + b[p - 1];
                        }
                }
                printf("%d\n", 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;
}

10815번: 숫자 카드

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


$O(n\lg n)$

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

$O(n)$

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

2143번: 두 배열의 합

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


$O(n^2\lg n)$

A,B의 부 배열의 합을 모두 구해놓고 이진 탐색으로 합이 T가 되는 쌍의 개수를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, s[500500], cnt, s1[1001], s2[1001], n, m;
long long r;
int main() {
        scanf("%d%d", &t, &n);
        for (int i = 1; i <= n; i++) {
                scanf("%d", s1 + i);
                s1[i] += s1[i - 1];
                for (int j = 0; j < i; j++) s[cnt++] = s1[i] - s1[j];
        }
        sort(s, s + cnt);
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) {
                scanf("%d", s2 + i);
                s2[i] += s2[i - 1];
                for (int j = 0; j < i; j++)
                    r += upper_bound(s, s + cnt, t - s2[i] + s2[j]) - lower_bound(s, s + cnt, t - s2[i] + s2[j]);
        }
        printf("%lld", r);
        return 0;
}