解法1: 重軽分解によるアプローチ

オフライン処理可能な問題特性を利用し、操作履歴から木構造を構築する。各ノードの解は根からそのノードまでのアイテムを用いた完全ナップサック問題と等価である。

深さ優先探索(DFS)実行時、再帰スタックにナップサック状態を保持する。空間計算量を削減するため、重軽分解(Heavy-Light Decomposition)を適用する。具体的には:

1. 各ノードで最終アクセスする子ノード(heavy child)を特別扱い
2. heavy child以外の処理時のみスタックに状態を保存
3. heavy child処理時はスタックを変更せず直接更新

これにより空間計算量をO(m log n)に改善可能。ナップサック処理は以下の構造体で実装:

struct Knapsack {
    int dp[MAX_M];
    Knapsack() { memset(dp, 0, sizeof(dp)); }
    void add(int value, int weight) {
        for (int i = weight; i <= capacity; i++)
            dp[i] = max(dp[i], dp[i - weight] + value);
    }
};

実装例

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 20000;
const int MAX_M = 20000;
const int ROOT = MAX_N + 1;

int capacity, query_count, item_count;
int values[MAX_N], weights[MAX_N];
int parent[MAX_N];
vector<int> children[MAX_N];
vector<int> queries[MAX_N];
int heavy_child[MAX_N], subtree_size[MAX_N];
vector<Knapsack> state_stack;

void precompute(int node = ROOT) {
    subtree_size[node] = 1;
    for (int child : children[node]) {
        precompute(child);
        subtree_size[node] += subtree_size[child];
        if (subtree_size[child] > subtree_size[heavy_child[node]])
            heavy_child[node] = child;
    }
}

void dfs(int node = ROOT) {
    for (int qid : queries[node])
        query_results[qid] = state_stack.back().dp[capacity];
    
    for (int child : children[node]) {
        if (child == heavy_child[node]) continue;
        state_stack.push_back(state_stack.back());
        state_stack.back().add(values[child], weights[child]);
        dfs(child);
        state_stack.pop_back();
    }
    
    if (heavy_child[node]) {
        state_stack.back().add(values[heavy_child[node]], weights[heavy_child[node]]);
        dfs(heavy_child[node]);
    }
}

解法2: ブロック分割による最適化

アイテム追加/削除操作を√nサイズのブロック単位で管理。主要なデータ構造:

struct BlockManager {
    struct BlockData {
        int dp[MAX_M];
        void update(int value, int weight) {
            for (int i = weight; i <= capacity; i++)
                dp[i] = max(dp[i], dp[i - weight] + value);
        }
    };
    
    vector<BlockData> block_data;
    int current_block = -1;
    
    void initialize() {
        block_data.push_back(BlockData());
        current_block = 0;
    }
};

ブロック跨ぎ処理の最適化戦略:

1. 隣接ブロック間移動時に前ブロックデータを保持
2. 2ブロック以上離れた時点で古いデータ削除
3. 削除操作時の再構築をブロック単位で遅延処理

計算量解析: O(n√m) 時間計算量と O(m√n) 空間計算量を達成。ブロックサイズB=√nとした場合、最悪時でもO(nm)を超えない。

const int BLOCK_SIZE = 141;

void process_add(int id) {
    int block_id = (id - 1) / BLOCK_SIZE;
    
    if (block_id != current_block) {
        manager.add_block(manager.get_last_block());
        current_block = block_id;
    }
    
    manager.current_block().add(values[id], weights[id]);
    
    if (block_id >= 2) 
        manager.clean_old_blocks(block_id - 2);
}

void process_remove(int id) {
    manager.remove_last();
    current_block = (id - 2) / BLOCK_SIZE;
    
    if (manager.block_size(current_block) == 1) 
        manager.rebuild_block(current_block);
}