Shortest Path DAG and Convex Hull Optimization

This problem involves processing a transportation network where we need to compute both the shortest travel time and the maximum possible delay while still arriving on time.

Solution Approach

First, we construct the shortest path DAG by running Dijkstra's algorithm from the source node. Any edge not part of a shortest path is removed. Each transportation line may be split into multiple segments in this DAG, requiring us to renumber these segments as independent entities.

After processing, we sort all nodes by they distance from the source. The DP state transition becomes:

dp[v] = max(dp[u] + (dist[v] - dist[u])²)

This is a classic convex hull trick scenario. We maintain lines of the form y = mx + b where m = -2*dist[u] and b = dp[u] + dist[u]². A Li Chao segment tree handles maximum quereis efficiently.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e6 + 5;

struct GraphEdge {
    int to;
    ll weight;
    int lineId;
};

vector<GraphEdge> graph[MAXN];
vector<ll> distanceArr;
vector<bool> visited;

struct DijkstraNode {
    int node;
    ll dist;
    bool operator<(const DijkstraNode& other) const {
        return dist > other.dist;
    }
};

void dijkstra(int start, int n) {
    distanceArr.assign(n + 1, INF);
    visited.assign(n + 1, false);
    priority_queue<DijkstraNode> pq;
    distanceArr[start] = 0;
    pq.push({start, 0});
    
    while (!pq.empty()) {
        int u = pq.top().node;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        
        for (auto& e : graph[u]) {
            if (distanceArr[e.to] > distanceArr[u] + e.weight) {
                distanceArr[e.to] = distanceArr[u] + e.weight;
                pq.push({e.to, distanceArr[e.to]});
            }
        }
    }
}

struct ConvexHullTrick {
    struct Line {
        ll slope, intercept;
        ll evaluate(ll x) const {
            return slope * x + intercept;
        }
    };
    
    struct SegmentNode {
        int leftChild, rightChild;
        int bestLine;
    };
    
    vector<Line> lines;
    vector<SegmentNode> segTree;
    vector<int> root;
    int lineCount = 0;
    int nodeCount = 0;
    
    void init(int size) {
        root.assign(size + 1, 0);
        lines.push_back({0, -INF});
    }
    
    int createNode() {
        segTree.push_back({0, 0, 0});
        return ++nodeCount;
    }
    
    bool isBetter(const Line& a, const Line& b, ll x) {
        return a.evaluate(x) > b.evaluate(x);
    }
    
    void update(int& node, ll l, ll r, int newLine) {
        if (!node) node = createNode();
        
        ll mid = (l + r) >> 1;
        if (isBetter(lines[newLine], lines[segTree[node].bestLine], mid)) {
            swap(newLine, segTree[node].bestLine);
        }
        
        if (l == r) return;
        
        if (isBetter(lines[newLine], lines[segTree[node].bestLine], l)) {
            update(segTree[node].leftChild, l, mid, newLine);
        } else if (isBetter(lines[newLine], lines[segTree[node].bestLine], r)) {
            update(segTree[node].rightChild, mid + 1, r, newLine);
        }
    }
    
    ll query(int node, ll l, ll r, ll x) {
        if (!node) return -INF;
        ll res = lines[segTree[node].bestLine].evaluate(x);
        if (l == r) return res;
        
        ll mid = (l + r) >> 1;
        if (x <= mid) return max(res, query(segTree[node].leftChild, l, mid, x));
        else return max(res, query(segTree[node].rightChild, mid + 1, r, x));
    }
    
    void addLine(ll slope, ll intercept, const vector<int>& nodes) {
        int lineId = ++lineCount;
        lines.push_back({slope, intercept});
        for (int node : nodes) {
            update(root[node], 0, 1e9, lineId);
        }
    }
};

ConvexHullTrick cht;
int n, m;
ll dp[MAXN];
int order[MAXN];
vector<int> segmentNodes[MAXN];
map<pair<int, int>, bool> inShortestPath[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    cht.init(n);
    
    for (int i = 1; i <= m; i++) {
        int k, prev;
        cin >> k >> prev;
        vector<int> path = {prev};
        
        for (int j = 1; j <= k; j++) {
            int time, next;
            cin >> time >> next;
            graph[prev].push_back({next, time, i});
            path.push_back(next);
            prev = next;
        }
    }
    
    dijkstra(1, n);
    
    for (int u = 1; u <= n; u++) {
        for (auto& e : graph[u]) {
            if (distanceArr[u] + e.weight == distanceArr[e.to]) {
                inShortestPath[e.lineId][{u, e.to}] = true;
            }
        }
    }
    
    int segmentCount = 0;
    for (int line = 1; line <= m; line++) {
        int start = -1;
        for (int i = 0; i + 1 < path.size(); i++) {
            int u = path[i], v = path[i + 1];
            if (inShortestPath[line][{u, v}]) {
                if (start == -1) start = i;
            } else {
                if (start != -1) {
                    segmentCount++;
                    for (int j = start; j <= i; j++) {
                        segmentNodes[path[j]].push_back(segmentCount);
                    }
                    start = -1;
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        order[i] = i;
    }
    sort(order + 1, order + n + 1, [](int a, int b) {
        return distanceArr[a] < distanceArr[b];
    });
    
    for (int i = 1; i <= n; i++) {
        int v = order[i];
        for (int seg : segmentNodes[v]) {
            dp[v] = max(dp[v], cht.query(cht.root[seg], 0, 1e9, distanceArr[v]) + distanceArr[v] * distanceArr[v]);
        }
        cht.addLine(-2 * distanceArr[v], dp[v] + distanceArr[v] * distanceArr[v], segmentNodes[v]);
    }
    
    cout << distanceArr[n] << " " << dp[n] << "\n";
    return 0;
}

Circular Barn and Divide-and-Conquer DP Optimization

Given a circular arrangement of rooms with animal counts, we need to place feeders to minimize total walking distance, breaking the circle at optimal starting points.

Solution Approach

We convert the circular problem to linear by duplicating the array. The cost function cost(l, r) = sum(i - l) * animals[i] satisfies the quadrangle inequality, enabling divide-and-conquer optimization.

For each starting position, we compute DP with k feeders using a recursive optimization that narrows the decision range at each step.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2005;
const int MAXK = 8;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, k;
ll animalCount[MAXN];
ll prefixCost[MAXN][MAXN];
ll dp[MAXK][MAXN];
ll finalAnswer = INF;

void optimize(int feederCount, int l, int r, int optL, int optR) {
    if (l > r) return;
    
    int mid = (l + r) >> 1;
    int bestPos = -1;
    dp[feederCount][mid] = INF;
    
    for (int i = optL; i <= min(mid, optR); i++) {
        ll candidate = dp[feederCount - 1][i - 1] + prefixCost[i][mid];
        if (candidate < dp[feederCount][mid]) {
            dp[feederCount][mid] = candidate;
            bestPos = i;
        }
    }
    
    optimize(feederCount, l, mid - 1, optL, bestPos);
    optimize(feederCount, mid + 1, r, bestPos, optR);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> animalCount[i];
        animalCount[n + i] = animalCount[i];
    }
    
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = i; j <= 2 * n; j++) {
            prefixCost[i][j] = prefixCost[i][j - 1] + animalCount[j] * (j - i);
        }
    }
    
    for (int start = 1; start <= n; start++) {
        for (int i = start - 1; i <= start + n - 1; i++) {
            for (int j = 0; j <= k; j++) {
                dp[j][i] = INF;
            }
        }
        dp[0][start - 1] = 0;
        
        for (int j = 1; j <= k; j++) {
            optimize(j, start, start + n - 1, start, start + n - 1);
        }
        
        finalAnswer = min(finalAnswer, dp[k][start + n - 1]);
    }
    
    cout << finalAnswer << "\n";
    return 0;
}

Dual-Stack Technique for Sliding Window Knapsack

Given a sequence of items with weights and values, find the shortest subarray where we can select items to achieve exactly target weight with total value within budget.

Solution Approach

The knapsack DP doesn't support efficient removal of elements. We simulate a queue using two stacks: left and right. Each stack entry stores the DP state from its bottom to top, enabling O(weight) merges.

When moving the right pointer, we push to the right stack. When moving the left pointer, we pop from the left stack. If the left stack empties, we transfer all elements from the right stack to the left stack, rebuilding DP states.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VLL = vector<ll>;
const int MAXN = 10005;
const int MAXW = 5005;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct StackEntry {
    int itemId;
    VLL dpState;
};

stack<StackEntry> leftStack, rightStack;
int n, targetWeight, budget;
int weightArr[MAXN], valueArr[MAXN];
ll answer = INF;

VLL updateDP(const VLL& prevState, int idx) {
    VLL newState = prevState;
    for (int i = targetWeight; i >= weightArr[idx]; i--) {
        newState[i] = min(newState[i], prevState[i - weightArr[idx]] + valueArr[idx]);
    }
    return newState;
}

bool isValid() {
    const VLL& leftDP = leftStack.top().dpState;
    const VLL& rightDP = rightStack.top().dpState;
    for (int i = 0; i <= targetWeight; i++) {
        if (leftDP[i] + rightDP[targetWeight - i] <= budget) return true;
    }
    return false;
}

void pushItem(stack<StackEntry>& st, int idx) {
    if (st.empty()) {
        VLL initial(targetWeight + 1, INF);
        initial[0] = 0;
        st.push({idx, initial});
    } else {
        VLL newDP = updateDP(st.top().dpState, idx);
        st.push({idx, newDP});
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> targetWeight >> budget;
    for (int i = 1; i <= n; i++) {
        cin >> weightArr[i] >> valueArr[i];
    }
    
    pushItem(leftStack, 0);
    pushItem(rightStack, 0);
    
    for (int left = 1, right = 0; left <= n; left++) {
        while (right < n && !isValid()) {
            pushItem(rightStack, ++right);
        }
        
        if (isValid()) {
            answer = min(answer, (ll)right - left + 1);
        }
        
        if (leftStack.top().itemId == 0) {
            while (rightStack.top().itemId != 0) {
                pushItem(leftStack, rightStack.top().itemId);
                rightStack.pop();
            }
        }
        leftStack.pop();
    }
    
    cout << (answer == INF ? -1 : answer) << "\n";
    return 0;
}

Tree DP with Heavy-Light Decomposition

Find maximum weight independent set on a tree with node weights and values, counting the number of optimal solutions.

Solution Approach

We use heavy-light decomposition to create a DFS order where heavy paths are contiguous. For each node, we identify "critical nodes" along its ancestor chain. The number of critical nodes per node is O(log n), allowing state compression.

DP states represent which critical nodes are selected. Transitions consider whether the current node is selected based on its parent's state.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 55;
const int MAXC = 5005;

struct DPNode {
    ll value;
    int count;
};

int testCases, nodeCount, capacity;
int nodeWeight[MAXN], nodeValue[MAXN];
int order[MAXN], revOrder[MAXN];
int subSize[MAXN], heavyChild[MAXN], parentArr[MAXN], head[MAXN];
vector<int> adj[MAXN];
vector<int> criticalNodes[MAXN];
DPNode dp[2][MAXN][MAXC];

void combine(DPNode& target, const DPNode& source) {
    if (target.value < source.value) {
        target = source;
    } else if (target.value == source.value) {
        target.count += source.count;
    }
}

void dfs1(int u, int p) {
    parentArr[u] = p;
    subSize[u] = 1;
    heavyChild[u] = 0;
    
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            subSize[u] += subSize[v];
            if (subSize[v] > subSize[heavyChild[u]]) {
                heavyChild[u] = v;
            }
        }
    }
}

int currentTime = 0;
void dfs2(int u, int p, int top) {
    order[u] = ++currentTime;
    revOrder[currentTime] = u;
    head[u] = top;
    
    for (int v : adj[u]) {
        if (v != p && v != heavyChild[u]) {
            dfs2(v, u, v);
        }
    }
    
    if (heavyChild[u]) {
        dfs2(heavyChild[u], u, top);
    }
}

void initializeDP() {
    for (int i = 1; i <= nodeCount; i++) {
        int current = i;
        while (current) {
            criticalNodes[i].push_back(current);
            current = parentArr[head[current]];
        }
    }
    
    for (int state = 0; state < 2; state++) {
        for (int j = 0; j <= capacity; j++) {
            dp[0][state][j] = {0, 0};
        }
    }
    dp[0][0][0] = {0, 1};
    dp[0][1][nodeWeight[revOrder[1]]] = {nodeValue[revOrder[1]], 1};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> testCases;
    for (int tc = 1; tc <= testCases; tc++) {
        cin >> nodeCount >> capacity;
        
        for (int i = 1; i <= nodeCount; i++) {
            cin >> nodeWeight[i] >> nodeValue[i];
            adj[i].clear();
            criticalNodes[i].clear();
        }
        
        for (int i = 1; i < nodeCount; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        dfs1(1, 0);
        dfs2(1, 0, 1);
        initializeDP();
        
        int cur = 0, prev = 1;
        for (int i = 2; i <= nodeCount; i++) {
            int node = revOrder[i];
            int prevNode = revOrder[i - 1];
            int nodeCritSize = criticalNodes[node].size();
            int prevCritSize = criticalNodes[prevNode].size();
            int parentPos = -1;
            vector<int> mapping(prevCritSize, -1);
            
            for (int j = 0; j < prevCritSize; j++) {
                int crit = criticalNodes[prevNode][j];
                if (crit == parentArr[node]) parentPos = j;
                for (int k = 0; k < nodeCritSize; k++) {
                    if (criticalNodes[node][k] == crit) {
                        mapping[j] = k;
                        break;
                    }
                }
            }
            
            for (int mask = 0; mask < (1 << nodeCritSize); mask++) {
                for (int j = 0; j <= capacity; j++) {
                    dp[cur][mask][j] = {0, 0};
                }
            }
            
            for (int prevMask = 0; prevMask < (1 << prevCritSize); prevMask++) {
                int curMask = 0;
                for (int j = 0; j < prevCritSize; j++) {
                    if ((prevMask & (1 << j)) && mapping[j] != -1) {
                        curMask |= (1 << mapping[j]);
                    }
                }
                
                for (int j = 0; j <= capacity; j++) {
                    if (dp[prev][prevMask][j].count == 0) continue;
                    
                    combine(dp[cur][curMask][j], dp[prev][prevMask][j]);
                    
                    if (!(prevMask & (1 << parentPos)) && j + nodeWeight[node] <= capacity) {
                        DPNode newState = {
                            dp[prev][prevMask][j].value + nodeValue[node],
                            dp[prev][prevMask][j].count
                        };
                        combine(dp[cur][curMask | 1][j + nodeWeight[node]], newState);
                    }
                }
            }
            
            swap(cur, prev);
        }
        
        cout << "Case " << tc << ":\n";
        for (int i = 1; i <= capacity; i++) {
            DPNode result = {0, 0};
            int lastNode = revOrder[nodeCount];
            for (int mask = 0; mask < (1 << criticalNodes[lastNode].size()); mask++) {
                combine(result, dp[prev][mask][i]);
            }
            cout << result.count << " ";
        }
        cout << "\n";
    }
    return 0;
}

Path Queries with Centroid Decomposition

Count paths in a tree where the sum of node values along the path is divisible by K.

Solution Approach

We use centroid decomposition to process queries offline. For each centroid, we maintain knapsack counts of path sums modulo K from the centroid to nodes in each subtree. Queries are answered by combining counts from different subtrees.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200005;
const int MAXK = 55;
const int MOD = 998244353;

struct Query {
    int u, v, id;
};

int n, K, qCount;
ll nodeVal[MAXN];
ll knapsack[MAXN][MAXK];
ll temp[MAXK];
int componentId[MAXN];
ll answer[MAXN];
int currentComponent = 0;

vector<int> tree[MAXN];
vector<Query> queries[MAXN];
vector<Query> pending[MAXN];
bool processed[MAXN];

int subtreeSize[MAXN], maxSubtree[MAXN];
int currentTreeSize, centroid;

void findCentroid(int u, int p) {
    subtreeSize[u] = 1;
    maxSubtree[u] = 0;
    
    for (int v : tree[u]) {
        if (v != p && !processed[v]) {
            findCentroid(v, u);
            subtreeSize[u] += subtreeSize[v];
            maxSubtree[u] = max(maxSubtree[u], subtreeSize[v]);
        }
    }
    
    maxSubtree[u] = max(maxSubtree[u], currentTreeSize - subtreeSize[u]);
    if (maxSubtree[u] < maxSubtree[centroid]) {
        centroid = u;
    }
}

void traverse(int u, int p, int comp) {
    componentId[u] = comp;
    for (int i = 0; i < K; i++) {
        knapsack[u][(i + nodeVal[u]) % K] = (knapsack[p][(i + nodeVal[u]) % K] + knapsack[p][i]) % MOD;
    }
    
    for (int v : tree[u]) {
        if (v != p && !processed[v]) {
            traverse(v, u, comp);
        }
    }
}

void processCentroid(int u) {
    for (int i = 0; i < K; i++) {
        knapsack[u][i] = 0;
    }
    knapsack[u][0] = 1;
    
    for (int v : tree[u]) {
        if (!processed[v]) {
            currentComponent++;
            traverse(v, u, currentComponent);
        }
    }
    
    for (auto& q : queries[u]) {
        if (componentId[q.u] != componentId[q.v]) {
            for (int i = 0; i < K; i++) {
                temp[(i + nodeVal[u]) % K] = (knapsack[q.v][(i + nodeVal[u]) % K] + knapsack[q.v][i]) % MOD;
            }
            for (int i = 0; i < K; i++) {
                answer[q.id] = (answer[q.id] + knapsack[q.u][i] * temp[(K - i) % K]) % MOD;
            }
        } else {
            pending[componentId[q.u]].push_back(q);
        }
    }
    queries[u].clear();
}

void decompose(int u) {
    processed[u] = true;
    processCentroid(u);
    
    for (int v : tree[u]) {
        if (!processed[v]) {
            currentTreeSize = subtreeSize[v];
            centroid = 0;
            findCentroid(v, u);
            findCentroid(centroid, u);
            queries[centroid] = pending[componentId[v]];
            pending[componentId[v]].clear();
            decompose(centroid);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> K;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) {
        cin >> nodeVal[i];
    }
    
    maxSubtree[0] = INT_MAX;
    currentTreeSize = n;
    findCentroid(1, 0);
    findCentroid(centroid, 0);
    
    cin >> qCount;
    for (int i = 1; i <= qCount; i++) {
        int u, v;
        cin >> u >> v;
        if (u == v) {
            answer[i] = 1 + (nodeVal[u] % K == 0);
        } else {
            queries[centroid].push_back({u, v, i});
        }
    }
    
    decompose(centroid);
    
    for (int i = 1; i <= qCount; i++) {
        cout << answer[i] << "\n";
    }
    return 0;
}

Tree Connection Counting DP

Count ways to reconnect a tree such that each node connects to an ancestor with no crossing edges, rooted at node n.

Solution Approach

Let dp[u][j] represent the number of ways when node u has j possible ancestor connections. For each child, the number of valid connections is limited by j+1. Prefix sums optimize the transition to O(n²).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 3005;
const int MOD = 998244353;

vector<int> tree[MAXN];
ll dp[MAXN][MAXN];
int n;

void solve(int u, int p) {
    for (int i = 1; i <= n; i++) {
        dp[u][i] = 1;
    }
    dp[u][0] = (u == n);
    
    for (int v : tree[u]) {
        if (v != p) {
            solve(v, u);
            for (int i = 0; i <= n; i++) {
                dp[u][i] = dp[u][i] * dp[v][i + 1] % MOD;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        dp[u][i] = (dp[u][i - 1] + dp[u][i]) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    
    solve(n, 0);
    cout << dp[n][0] << "\n";
    return 0;
}

Kangaroo Packing DP

Count ways to pack kangaroos into each other's pouches following size constraints.

Solution Approach

Sort kangaroos by size. For each kangaroo i, find the largest pouch p_i that can hold it. The DP state dp[i][j][k] tracks processed kangaroos, those already packed, and those needing pouches. Transitions hendle ignoring, packing into needy kangaroos, or packing into available pouches.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 305;
const int MOD = 1e9 + 7;

ll sizeArr[MAXN], capacityArr[MAXN];
ll dp[2][MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> sizeArr[i] >> capacityArr[i];
    }
    
    sort(sizeArr + 1, sizeArr + n + 1);
    sort(capacityArr + 1, capacityArr + n + 1);
    reverse(sizeArr + 1, sizeArr + n + 1);
    reverse(capacityArr + 1, capacityArr + n + 1);
    
    int cur = 0, prev = 1;
    dp[prev][0][0] = 1;
    
    for (int i = 1, p = 0; i <= n; i++) {
        while (p < n && sizeArr[i] < capacityArr[p + 1]) p++;
        
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                dp[cur][j][k] = 0;
            }
        }
        
        for (int j = 0; j < i; j++) {
            for (int k = 0; j + k <= p; k++) {
                dp[cur][j][p - j] = (dp[cur][j][p - j] + dp[prev][j][k]) % MOD;
                if (k > 0) {
                    dp[cur][j + 1][k - 1] = (dp[cur][j + 1][k - 1] + dp[prev][j][k] * k) % MOD;
                }
                dp[cur][j + 1][k] = (dp[cur][j + 1][k] + dp[prev][j][k] * (p - j - k)) % MOD;
            }
        }
        
        swap(cur, prev);
    }
    
    ll answer = 0;
    for (int i = 0; i <= n; i++) {
        answer = (answer + dp[prev][i][0]) % MOD;
    }
    
    cout << answer << "\n";
    return 0;
}

Binary Alarm System for Range Monitoring

Monitor multiple alarms that trigger when the sum of certain array elements exceeds thresholds, with range increments.

Solution Approach

Each alarm tracks the sum of elements at positions divisible by its factor. We maintain binary levels based on how close each sum is to its threshold. When elements update, we propagate changes through alarm levels, triggering those that exceed thresholds.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 5;
const int LOG = 61;

vector<ll> factorAlarms[MAXN];
vector<ll> alarmLevels[MAXN][LOG];
vector<int> primeFactors[MAXN];
vector<ll> triggeredAlarms;
ll levelThreshold[MAXN], currentLevel[MAXN];
bool isTriggered[MAXN];
ll arr[MAXN];
int n, q;
ll lastAnswer = 0, alarmCount = 0;

ll computeSum(int alarmId, ll shift) {
    ll total = 0;
    for (int pos : factorAlarms[alarmId]) {
        total += arr[pos] + (1LL << shift) - (((1LL << shift) - 1) & arr[pos]) - 1;
    }
    return total;
}

void updatePosition(int pos, ll delta) {
    ll mask = arr[pos] ^ (arr[pos] + delta);
    arr[pos] += delta;
    
    for (int bit = 0; (1LL << bit) <= delta || (mask & (1LL << bit)); bit++) {
        vector<ll> temp;
        temp.swap(alarmLevels[pos][bit]);
        
        for (ll alarmId : temp) {
            if (isTriggered[alarmId] || currentLevel[alarmId] != bit) continue;
            
            if (computeSum(alarmId, 0) >= levelThreshold[alarmId]) {
                isTriggered[alarmId] = true;
                triggeredAlarms.push_back(alarmId);
            } else {
                while (currentLevel[alarmId] > 0 && computeSum(alarmId, currentLevel[alarmId]) >= levelThreshold[alarmId]) {
                    currentLevel[alarmId]--;
                }
                
                if (currentLevel[alarmId] == bit) {
                    alarmLevels[pos][bit].push_back(alarmId);
                } else {
                    for (int factorPos : factorAlarms[alarmId]) {
                        alarmLevels[factorPos][currentLevel[alarmId]].push_back(alarmId);
                    }
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    
    for (int i = 2; i <= n; i++) {
        if (primeFactors[i].empty()) {
            for (int j = i; j <= n; j += i) {
                primeFactors[j].push_back(i);
            }
        }
    }
    
    for (int i = 1; i <= q; i++) {
        int type;
        ll x, v;
        cin >> type >> x >> v;
        v ^= lastAnswer;
        
        if (type == 1) {
            alarmCount++;
            factorAlarms[alarmCount] = primeFactors[x];
            
            if (v == 0) {
                triggeredAlarms.push_back(alarmCount);
            } else {
                levelThreshold[alarmCount] = computeSum(alarmCount, 0) + v;
                currentLevel[alarmCount] = 60;
                
                while (currentLevel[alarmCount] > 0 && computeSum(alarmCount, currentLevel[alarmCount]) >= levelThreshold[alarmCount]) {
                    currentLevel[alarmCount]--;
                }
                
                for (int pos : factorAlarms[alarmCount]) {
                    alarmLevels[pos][currentLevel[alarmCount]].push_back(alarmCount);
                }
            }
        } else {
            for (int factor : primeFactors[x]) {
                updatePosition(factor, v);
            }
            
            cout << (lastAnswer = triggeredAlarms.size()) << " ";
            sort(triggeredAlarms.begin(), triggeredAlarms.end());
            for (ll id : triggeredAlarms) {
                cout << id << " ";
            }
            cout << "\n";
            triggeredAlarms.clear();
        }
    }
    return 0;
}