1665번: 화물열차

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


$O(nm\lg {nm})$

화물을 다항식으로 나타내보자.
a번째에 화물이 있다면 x^a을 더하면 된다.
예를 들어 1,2,4번째에 화물이 존재한다면 이를 나타내는 함수는 x+x^2+x^4이 된다.
이렇게 놓으면 대충 감이 올 수 있는데, 답은 화물 A, B를 나타내는 다항식을 곱한 뒤에 가장 큰 계수가 된다.
이것이 왜 성립하는지는 알아서 생각해보도록 하자.
문제에서 구간이 10억까지 주어지므로 구간을 다항식으로 나타낼 때 등비합 공식을 이용할 필요가 있다.
[a,b] 구간에 존재함은 (x^a-x^(b+1))/(1-x)로 나타낼 수 있다.
A,B 곱한 분수식에 대해 생각해보자. 분자에는 항이 최대 4nm개가 있고 분모는 (1-x)^2일 것이다.
이때 1/(1-x)^2은 (2H0+2H1x+2H2x^2+ ... ) 즉 (1+2x+3x^2 + ...)으로 바꾸어 사용할 수 있다.
분모를 바꾼식은 지수승과 계수가 1씩 증가하는 형태라 무작정 처음의 분자식과 곱해서 구할 필요가 없다.
처음 분자식의 지수승이 증가하는 형태로 오름차순 정리한 다음,
계수를 누적하고 이 값과 지수승이 변하는 만큼의 곱을 누적하면 그 때마다 어떤 지수승의 항의 계수를 구할 수 있다.
모든 항의 계수를 구할 필요는 없고 처음 분자식에 존재하는 항에 대해서만 구하면 된다.(이 부분을 조금 더 생각)
참고로 x^a의 계수는 a-1번 움직였을 때의 겹치는 개수이다.

#include<stdio.h>
#include<algorithm>
#define f first
#define s second
using namespace std;
typedef long long ll;
const int MAX_N = 1e3;
int n, m, cnt;
pair<int, int> p1[MAX_N], p2[MAX_N], a[MAX_N*MAX_N * 4];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p1[i].f, &p1[i].s);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d %d", &p2[i].f, &p2[i].s);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[cnt++] = { p1[i].f + p2[j].f,1 };
            a[cnt++] = { p1[i].f + p2[j].s + 1,-1 };
            a[cnt++] = { p1[i].s + p2[j].f + 1,-1 };
            a[cnt++] = { p1[i].s + p2[j].s + 2,1 };
        }
    }
    sort(a, a + cnt);
    ll sum, t = 0, r = 0, idx;
    sum = a[0].s;
    for (int i = 1; i < cnt; i++) {
        if (a[i - 1].first == a[i].first) {
            sum += a[i].second;
            continue;
        }
        t += sum;
        if (t > r) r = t, idx = a[i - 1].first - 1;
        t += sum*(a[i].first - a[i - 1].first - 1);
        if (t > r) r = t, idx = a[i].first - 2;
        sum += a[i].second;
    }
    if (t + sum > r) idx = a[cnt - 1].first - 1;
    printf("%d", idx);
    return 0;
}