11511번: RELATIVNOST

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


$O((N+Q\lg N)*c^2)$

문제에서 c가 매우 작다는 점을 확인하자.
이 점을 이용해 어떤 구간에서 색물감을 산사람 수 0...c-1, 그리고 c이상 산 사람 총 c+1개의 상태를 가지고 dp를 구현할 수 있다.
많은 쿼리를 처리해야 하므로 효율적인 자료구조를 사용해야 한다. 아래 소스에서는 tournament tree를 사용했다.
[l,r](=h)의 구간을 계산해보자, 구간 [l,m](=p) [m+1,r](=q)에 대해서는 이미 구해졌다 가정한다.(m=(l+r)/2)
다음 점화식이 성립한다.
dp[i][j]: i구간에서 색물감을 j명이 산 경우의 수(j=c이면 c이상을 산 사람을 의미함)
dp[h][j]에서
j<c이면 sum(dp[p][k]*dp[q][j-k])
j=c이면 sum(j+k>=c) (dp[p][j]*dp[q][k])

쿼리가 들어오면, 자신에 해당했던 구간의 dp값을 갱신해주면 된다. 자료구조의 특성상 이 때마다 걸리는 시간 복잡도는 O(lgN*c^2)이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5, MAX_C = 20, mod = 10007;
int n, c, q, dp[MAX_N * 2][MAX_C + 1];
void update(int h) {
    fill(dp[h], dp[h] + c + 1, 0);
    for (int i = 0; i <= c; i++)
        for (int j = 0; j <= c; j++)
            dp[h][min(i + j, c)] = (dp[h][min(i + j, c)] + dp[h * 2][i] * dp[h * 2 + 1][j]) % mod;
}
int main() {
    scanf("%d %d", &n, &c);
    for (int i = n; i <2 * n; i++) scanf("%d", &dp[i][1]), dp[i][1] %= mod;
    for (int i = n; i <2 * n; i++) scanf("%d", &dp[i][0]), dp[i][0] %= mod;
    for (int i = n - 1; i; i--) update(i);
    scanf("%d", &q);
    for (int i = 0, x, y, z; i < q; i++) {
        scanf("%d %d %d", &x, &y, &z);
        dp[x + n - 1][1] = y%mod; dp[x + n - 1][0] = z%mod;
        for (int i = (x + n - 1) / 2; i; i /= 2) update(i);
        printf("%d\n", dp[1][c]);
    }
    return 0;
}