我复活辣！

D1T1 - 分糖果

题目大意.

有 $n$ 个元素，每个元素 $a_i$ 有一个"容量" $c_i$，一开始元素全为 $0$。你要支持 $q$ 次操作：区间加一个整数 $v$（可以为负），然后每个元素与 $0$ 取 max，与 $c_i$ 取 min（这个过程下面称为校正）。

最后你要输出所有元素的值。

$n,q\le 2\times10^5$。时限 4s。

硬分块即可，不多讲了。

然而有个十分合理的一只 log 做法：

想象每个元素对应一个下标相同却没有校正过程的"自由元素"，然后我们把原元素和其对应自由元素比较。问题就变成：

如何确定每个元素最后一次撞到上下边界是什么时候。

我们这里认为：初始状态算撞了一次下边界；从下边界横跳一下又碰到下边界不算是撞了两次，上亦然。

那么，两次撞边界之间的时间段中，对应自由元素的最大值和最小值之差必定 $\ge c_i$。而若某一时间段内，对应自由元素的最大值和最小值之差 $\ge c_i$，那么必定有至少两次撞击。

于是也就容易用线段树定位出倒数第二次撞击了，进而得出最后一次撞击。

又可见 $i$ 和 $i+1$ 所用的线段树是十分相似的，$i\leftarrow i + 1$ 时直接小修一下即可。

​x
//从马爷爷那里贺的厉害实现
#include<bits/stdc++.h>
using namespace std;
​
typedef vector<int> vec;
typedef long long ll;
​
const int maxn = 200005;
​
int n, m;
ll S;
vector<pair<int, int> > Q[maxn];
​
namespace SegT {
    struct node {
        ll vmax, vmin;
        ll lzy;
        node operator + (const node b) const {
            return (node){max(vmax, b.vmax), min(vmin, b.vmin), 0};
        }
        void add(const ll V) {
            vmax += V, vmin += V, lzy += V;
        }
    } T[maxn << 2];
    void pushdown(int x) {
        T[x << 1].add(T[x].lzy);
        T[x << 1 | 1].add(T[x].lzy);
        T[x].lzy = 0;
    }
    void update(int x, int l, int r, int L, int R, int V) {
        if (L <= l && r <= R) return T[x].add(V);
        pushdown(x);
        int mid = (l + r) >> 1;
        if (L <= mid) update(x << 1, l, mid, L, R, V);
        if (R > mid) update(x << 1 | 1, mid + 1, r, L, R, V);
        T[x] = T[x << 1] + T[x << 1 | 1];
    }
    ll query(int x, int l, int r, int C, ll qmin, ll qmax) {
        if (l == r) {
            if (T[x].vmax > S) {
                assert(S - qmin <= C);
                return S - qmin;
            }
            assert(C - (qmax - S) >= 0);
            return C - (qmax - S);
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        ll  tqmin = min(qmin, T[x << 1 | 1].vmin), 
            tqmax = max(qmax, T[x << 1 | 1].vmax);
        if (tqmax - tqmin <= C)
            return query(x << 1, l, mid, C, tqmin, tqmax);
        return query(x << 1 | 1, mid + 1, r, C, qmin, qmax);
    }
}
​
vec distribute_candies(vec c_, vec l_, vec r_, vec v_) {
    n = c_.size(); m = l_.size();
    vec ans; ans.resize(n);
    for (int i = 0; i < m; i++)
        Q[l_[i]].emplace_back(i, v_[i]),
        Q[r_[i] + 1].emplace_back(i, -v_[i]);
    
    for (int i = 0; i < n; i++) {
        for (auto qaq : Q[i])
            S += qaq.second,
            SegT::update(1, 0, m, qaq.first + 1, m, qaq.second);
        if (SegT::T[1].vmax - SegT::T[1].vmin <= c_[i])
            ans[i] = S - SegT::T[1].vmin;
        else ans[i] = SegT::query(1, 0, m, c_[i], 0x3f3f3f3f3f3f3f3fLL, -0x3f3f3f3f3f3f3f3fLL);
    }
    return ans;
}

D1T2 - 钥匙

题目大意.

现有 $n$ 个房间、$m$ 条无向边和 $n$ 类钥匙。每个房间中都有一把钥匙；每条边都需要你拥有指定的钥匙才能通过（钥匙不消耗）。

如果你一无所有地出现在 $i$ 号房间（当然，你可以立即捡起 $i$ 号房间中的钥匙），称你能到达的房间集合为 $p(i)$。

求使 $|p(i)|$ 最小的 $i$。若有多个，请把它们全部输出。

$n,m\le 3\times10^5$。

这个问题问的就很有猫腻，努力想一想和它相关的做法。

观察 1. 显然，如果 $u$ 能到达 $v$ 那么 $p(v)\subseteq p(u)$。于是，若 $|p(u)|$ 最小，那么对于任意 $v\in p(u)$ 必然有 $p(v)=p(u)$。

观察 2. 一旦发现两个点能互相到达，那么它们从此以后永远等价。

于是考虑维护一些互相等价的块，这些块之间构成一个 DAG。而我们想知道的是每个节点能否再扩展出边：如果形成环就说明这个环应当缩掉。

听起来很美好，但是怎么扩展边需要精细一点的考虑。

• 直接维护钥匙列表，以及每把钥匙维护钥匙对应的边的列表；（把所需钥匙作为关键字用 set 维护，合并的时候启发式合并就好了，你要相信评测机！！！）（当然线段树合并也合理）
• 扩展边的时候分钥匙考虑即可。

当然实际上我们也不需要 DAG 了，一条链就行。

代码好像没什么意义，先鸽为敬。

D1T3 - 喷泉公园

题目大意.

二维平面上有 $n$ 座喷泉，坐标各为 $(x_i,y_i)$。保证 $x_i,y_i$ 皆为偶数。

你要摆放 $n-1$ 条道路。每条道路都是一个长度为 $2$ 的横向或纵向的线段，且必须恰好连接两座不同的喷泉。你要保证你的道路使所有喷泉连通。

对于每条道路，都要分配一个长椅。对于道路 $(x,y)-(x,y+2)$，长椅可以摆放在 $(x+1,y+1)$ 或 $(x-1,y+1)$；横向的道路类似。道路不能共享长椅。

请判断：是否存在一种合法的建造道路和长椅的方案。如果存在，你还需要输出任意一组解。

有个 Subtask 是没有 $2\times 2$ 的喷泉方格，这背后肯定有猫腻。

打开 mspaint.exe，随便弄一组样例，然后瞎画一下，你会发现有个策略非常 nb：把长椅安置点黑白染色，白的只给横路用，黑的只给竖路用。这种情况只会在有两条紧挨的横/竖路时无法成功分配，然而它不会出现。

那么现在考虑如果有 $2\times 2$ 的喷泉方格该怎么办。回忆：白格不能有两条横边，黑格不能有两条竖边；我们要毙掉一条。结果发现按精湛细腻的顺序依次毙就做完了。

xxxxxxxxxx
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
​
typedef vector<int> vec;
#define pb_ push_back
​
const int maxn = 200005;
int n;
int fa[maxn];
​
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
​
map<int, int> id[maxn];
set<int> used[maxn];
​
vec ansu, ansv, ansa, ansb;
void add_E(int u, int v, int x, int y) {
    ansu.pb_(u - 1), ansv.pb_(v - 1);
    ansa.pb_(x), ansb.pb_(y);
    used[y].insert(x);
}
​
int construct_roads(vec Xp, vec Yp) {
    n = Xp.size();
    for (int i = 1; i <= n; i++)
        id[Yp[i - 1]][Xp[i - 1]] = i,
        fa[i] = i;
    for (int y = maxn - 5; y >= 0; y -= 2) {
        for (auto _ : id[y]) {
            int x = _.first, u = _.second;
            if (!id[y + 2].count(x)) continue;
            int v = id[y + 2][x];
            if (find(u) == find(v)) continue;
            fa[find(u)] = find(v);
            if ((x ^ y) & 2)
                add_E(u, v, x + 1, y + 1);
            else
                if (!used[y + 1].count(x - 1))
                    add_E(u, v, x - 1, y + 1);
                else add_E(u, id[y][x - 2], x - 1, y - 1);
        }
        for (auto _ : id[y]) {
            int x = _.first, u = _.second;
            if (!id[y].count(x - 2)) continue;
            int v = id[y][x - 2];
            if (find(u) == find(v)) continue;
            fa[find(u)] = find(v);
            if ((x ^ y) & 2) {
                if (!used[y + 1].count(x - 1))
                    add_E(u, v, x - 1, y + 1);
            }
            else
                add_E(u, v, x - 1, y - 1);
        }
    }
    if ((int)ansu.size() < n - 1) return 0;
    build(ansu, ansv, ansa, ansb);
    return 1;
}

D2T1 - 修改 DNA

题意懒得写了，思博题。

xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;
​
int S[100005][3][3];
int qaq(char c) {
    if (c == 'A') return 0;
    if (c == 'T') return 1;
    return 2;
}
int n;
void init(string a_, string b_) {
    n = a_.size();
    for (int i = 1; i <= n; i++) {
        for (int d1 = 0; d1 < 3; d1++)
        for (int d2 = 0; d2 < 3; d2++)
            S[i][d1][d2] = S[i - 1][d1][d2];
        S[i][qaq(a_[i - 1])][qaq(b_[i - 1])]++;
    }
}
int get_distance(int l, int r) {
    int s[3][3];
    for (int d1 = 0; d1 < 3; d1++)
    for (int d2 = 0; d2 < 3; d2++)
        s[d1][d2] = S[r + 1][d1][d2] - S[l][d1][d2];
    int ans = 0;
    for (int d1 = 0; d1 < 3; d1++)
    for (int d2 = d1 + 1; d2 < 3; d2++) {
        int w = min(s[d1][d2], s[d2][d1]);
        ans += w, s[d1][d2] -= w, s[d2][d1] -= w;
    }
    if (s[0][1] != s[1][2] || s[1][2] != s[2][0]) return -1;
    ans += 2 * s[0][1];
    if (s[1][0] != s[2][1] || s[2][1] != s[0][2]) return -1;
    ans += 2 * s[1][0];
    return ans;
}

D2T2 - 地♂牢游♂戏

题目大意.

现在有一个 $n + 1$ 个房间的黑暗且深邃的地牢和 $n$ 个敌人，第 $i$ 号敌人恰处在 $i$ 号房间，$n+1$ 号房间是出口。

一个敌人有四个属性 $s,p,u,v$。主角有一个属性，称为能力值。进入房间时会遭遇战斗：

• 如果主角当前的能力值大于等于这个敌人的 $s$，那么主角会战胜它（但是敌人不消失，再次进入时还是会遭遇战斗），其能力值 $+=s$，并进入房间 $u$。保证 $s\ge 1$，$u$ 大于当前房间编号。
• 否则主角会战败，其能力值 $+=p$，并进入房间 $v$。保证 $p\ge 1$。

显然游戏总是以主角走出地牢告终。现在有 $q$ 组询问：若英雄初始能力值为 $z$，一开始进入的房间为 $x$，问主角走出地牢时的能力值是多少。

$n\le 4\times10^5,q\le5\times10^4$。

保证 $u$ 大于当前房间编号我可以理解，算是保证游戏必定结束；但 $s$ 一人身兼多职就很有问题了，这背后肯定又有猫腻。

答案是：如果有一个怪原来打不过现在打过了，那打完之后你的能力值和原来比至少翻倍了。也就是说这种情况最多发生 $\log$ 次。

然而尴尬的是我们难以得知这 $\log$ 次究竟是打败了谁，也不知道当时的能力值是多少。于是我们干脆把所有怪按 $(2^i,2^{i+1}]$ 分段，建出能力值为 $2^i$ 时的图（一个基环树森林）。

• $s\le 2^i$ 的怪不会出现偏差，与它们相遇的结果在我们从 $2^i$ 升级到 $2^{i+1}$ 的过程中不会变动，就是赢；

• 同理 $s>2^{i+1}$ 的怪也只是输。

• $s\in(2^i,2^{i+1}]$ 的怪和我们的输赢关系的确会变动，但我们用到这种变动了的输赢关系最多只有一次，打完就晋级了。问题在于如何定位这场"渡劫战"。

• • 考虑倍增。如果我们把这 $x$ 步走完后的能力值大于路径上的能力值最低的同级怪，那不免会让人产生疑虑，所以改成考虑 $x/2$。有点像 LCA 问题。

最后我们遇到了一个尖♂锐的问题：上面这个做法，空间 $O(\log n\cdot n\cdot \log w)$，算一下常数就会发现过不去（倍增要记路径上的总和、最小值、目的地）……自然是用时间换空间，改成按 $16^i$ 分段，每次晋级最多要击败 $15$ 次。反正小力调参就行了。

代码如下。

xxxxxxxxxx
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
​
typedef vector<int> vec;
typedef long long ll;
​
const int inf = 0x3f3f3f3f, maxn = 400005;
​
const int B = 16, L = 7;
​
struct node {
    int tgt;
    ll sum;
    int req;
    node operator + (const node b) const {
        return (node){
            b.tgt, sum + b.sum, 
            b.req == inf ? req : (int)max(0LL, min((ll)req, b.req - sum))
        };
    }
} f[L][25][maxn];
int pB[L];
​
int n;
int s[maxn], p[maxn], w[maxn], l[maxn];
​
void get_ST(int X, node g[][maxn]) {
    for (int i = 0; i < n; i++)
        if (X >= s[i])
            g[0][i] = {w[i], s[i], inf};
        else 
            g[0][i] = {l[i], p[i], s[i]};
    for (int j = 1; j < 25; j++)
    for (int i = 0; i < n; i++)
        g[j][i] = g[j - 1][i] + g[j - 1][g[j - 1][i].tgt];
}
​
void init(int n_, vec s_, vec p_, vec w_, vec l_) {
    n = n_;
    for (int i = 0; i < n; i++)
        s[i] = s_[i], p[i] = p_[i], w[i] = w_[i], l[i] = l_[i];
    w[n] = n; l[n] = n;
    for (int d = 0; d < L; d++) {
        if (d == 0) pB[d] = 1; else pB[d] = pB[d - 1] * B;
        get_ST(pB[d], f[d]);
    }
    return;
}
​
ll simulate(int x, int z_) {
    ll z = z_;
​
    int i = 0;
    while (1) {
        while (i + 1 < L && z >= pB[i + 1]) i++;
        for (int j = 24; j >= 0; j--) {
            if (f[i][j][x].tgt == n) continue;
            if (f[i][j][x].req != inf && f[i][j][x].req <= z) continue;
            z += f[i][j][x].sum;
            x = f[i][j][x].tgt;
        }
        
        if (z >= s[x]) z += s[x], x = w[x];
        else z += p[x], x = l[x];
        if (x == n) return z;
    }
}

D2T3 - 位移寄存器

题目大意.

现在你有 $100$ 个 $2000$ 位二进制数，称为寄存器，你可以对这些寄存器做如下几种操作：

• move 操作：把某个寄存器的值复制到另一个寄存器中。
• store 操作：把某个寄存器的值赋为一个由你指定的常数。
• not/left/right 操作：把某个寄存器按位取反/左移指定常数次/右移指定常数次（移出范围地的位直接消失）的结果赋到另一个寄存器中。
• and/or/xor/add 操作：把某两个寄存器按位与/按位或/按位异或/加（这里的加法模 $2^{2000}$）的结果赋到另一个寄存器中。

你要完成以下两个任务：

• 现有 $100$ 个 $10$ 位二进制数，按顺序存储在 $0$ 号寄存器中，你要在 $150$ 步操作内找到其中的最大值。
• 现有 $100$ 个 $10$ 位二进制数，按顺序存储在 $0$ 号寄存器中，你要在 $4000$ 步操作内将它们排序。

参考资料：这里

观察 0. 巨大位数的寄存器，自然提醒我们要并行处理。

观察 1. 我们没有 if。看来得强行搞点数字魔术了。（上期回顾）

Part 1 - 两个数字的 max 和 min

让我们仔细想一想，有没有什么办法能不用 if 搞出 max 和 min。一个看起来比较有前途的方法是

那么问题就变成求绝对值 $|x|$。

• 首先，我们读取 $x$ 的符号位 x >> 10，记其为 $w$；
• 如果这一位为 $0$，那么我们不对 $x$ 取反；否则对 $x$ 取反。看似要个 if，实际上可以考虑妙用一下加法会吃最高位的设定：x ^ ((~w) + 1)。哎呀其实不就是弄了个 $-w$ 吗。

顺便，这样得到的 $-w$ 实际上告诉了我们原数列的大小关系，也就提示了一个常数更小的做法。

完 全 胜 利

然而还是过不去！怎么办？

Part 2 - 并行求 max 和 min

其实就是并行求绝对值。

• 仍然是读取符号位，先 >> 10。虽然第一个数的非符号位确实被清了，但别的还没有，所以这次我们再与上一个 ...00100000000010000000001。
• 我们要考虑一下怎么给这个并行 $w$ 取反。之前我们利用了加法会吃最高位的设定，但如果这里再用就会污染其他元素。所以我们这里不完全取反而是异或上 ...1110111111111101111111111。然后第 $11i$ 位就会有偏差，恰好是异或上 ...00010000000001000000000 就能修正。这样就能成功对 $x$ 并行"条件取反"了。

常数大点没关系，反正是并行啊！！！这效率多顶。

对于原题，我们只需要把奇数编号的元素和偶数编号的元素取 max 得到新序列，再继续取 max 下去。这还提示我们不用手动添加符号位：原来放偶数编号元素的位置可以给我们随便污染。

Part 3 - 排序问题

考虑把原序列分成两半 $a,b$ 并应用上面的神奇"并行 max/min"，这样 $a_i,b_i\rightarrow\min(a_i,b_i),\max(a_i,b_i)$。自然想到 $a$ 是原来下标为奇数的所有元素，$b$ 反之。也就是把所有 $2k+1,2k+2$ 摆正。

结果发现这种排序的第二轮是原地 tp，那么想到把 $a,b$ 反一下再移一位（把所有 $2k+2,2k+3$ 摆正）。一看这个排序好像还真的挺有道理，于是就过了。

下面瞎实现了一下，sub0 极限数据 128 步，sub1 极限数据 2887 步。

xxxxxxxxxx
#include "registers.h"
#include<bits/stdc++.h>
using namespace std;
​
int n, k;
​
namespace SUBTASK0 {
const int getr0 = 99, neg = 98, add1 = 97;
const int r = 0;
const int r0 = 1, r1 = 2;
const int r0mr1 = 4;
const int w = 5;
void init(int L) {
    vector<bool> tmp; tmp.resize(2000);
    for (int i = 0; i < n; i++) if (i % L == 0)
    for (int j = 0; j < k; j++)
        tmp[i * k + j] = 1;
    append_store(getr0, tmp); 
    
    for (int i = 0; i < 2000; i++) tmp[i] = 0;
    for (int i = 0; i < n; i++) if (i % L == 0)
    for (int j = 0; j <= k; j++)
        tmp[i * k + j] = 1;
    append_store(neg, tmp); 
    
    for (int i = 0; i < 2000; i++) tmp[i] = 0;
    for (int i = 0; i < n; i++) if (i % L == 0)
        tmp[i * k] = 1;
    append_store(add1, tmp); 
}
void getneg(int ans, int d) {
    append_xor(ans, d, neg);
    append_add(ans, ans, add1); // k + 1 可能是脏的
}
​
void solve() {
    int x = 1; while (x < n) x <<= 1;
    if (x != n) {
        vector<bool> tmp; tmp.resize(2000);
        for (int i = n; i < x; i++)
        for (int j = 0; j < k; j++)
            tmp[i * k + j] = 1;
        int tmpv = 23;
        append_store(tmpv, tmp);
        append_or(r, r, tmpv);
        n = x;
    }
​
    if (k == 1) {
        int tmpr = 34;
        for (int i = 0; 1 << i < n; i++)
            append_right(tmpr, r, 1 << i),
            append_and(r, r, tmpr);
        return;
    }
    
    for (int i = 0; 1 << i < n; i++) {
        init(1 << (i + 1));
        // get r0, get r1
        append_and(r0, r, getr0);
        append_right(r1, r, k << i);
        append_and(r1, r1, getr0);
​
        // get r0mr1
        getneg(r0mr1, r1);
        append_add(r0mr1, r0, r0mr1);
​
        // get w
        append_right(w, r0mr1, k);
        append_and(w, w, add1);
​
        // get tw : > -> 0, < -> 1
        int tw = 6, revtw = 7;
        getneg(tw, w);
        append_and(tw, tw, neg); // 清洗 k + 1
        append_xor(revtw, tw, neg);
​
        // get new r
        append_and(r0, r0, tw); append_and(r1, r1, revtw);
        append_add(r, r0, r1);
    }
}
}
​
namespace SUBTASK1 {
const int getr0 = 99, neg = 98, add1 = 97;
const int LOW = 96, HIH = 95;
const int r = 0;
const int r0 = 1, r1 = 2;
const int r0mr1 = 4;
const int w = 5;
void init(int L) {
    vector<bool> tmp; tmp.resize(2000);
    for (int i = 0; i < n; i++) if (i % L == 0)
    for (int j = 0; j < k; j++)
        tmp[i * k + j] = 1;
    append_store(getr0, tmp); 
    
    for (int i = 0; i < 2000; i++) tmp[i] = 0;
    for (int i = 0; i < n; i++) if (i % L == 0)
    for (int j = 0; j <= k; j++)
        tmp[i * k + j] = 1;
    append_store(neg, tmp); 
    
    for (int i = 0; i < 2000; i++) tmp[i] = 0;
    for (int i = 0; i < n; i++) if (i % L == 0)
        tmp[i * k] = 1;
    append_store(add1, tmp);
​
    for (int i = 0; i < 2000; i++) tmp[i] = 0;
    for (int j = 0; j < k; j++)
        tmp[j] = 1;
    append_store(LOW, tmp);
​
    for (int i = 0; i < 2000; i++) tmp[i] = 0;
    for (int j = 0; j < k; j++)
        tmp[(n - 1) * k + j] = 1;
    append_store(HIH, tmp);
}
void getneg(int ans, int d) {
    append_xor(ans, d, neg);
    append_add(ans, ans, add1);
}
​
void solve() {
    int x = 1;
    while (x < n) x <<= 1;
    if (x != n) {
        vector<bool> tmp; tmp.resize(2000);
        for (int i = n; i < x; i++)
        for (int j = 0; j < k; j++)
            tmp[i * k + j] = 1;
        int tmpv = 23;
        append_store(tmpv, tmp);
        append_or(r, r, tmpv);
        n = x;
    }
    if (k == 1) {
        vector<bool> tmp; tmp.resize(2000);
        tmp[0] = 1;
        int qaq = 19, sum = 20, one = 21;
        append_store(one, tmp);
        for (int i = 0; i < n; i++)
            append_and(qaq, r, one),
            append_add(sum, sum, qaq),
            append_right(r, r, 1);
        for (int i = 0; i < 2000; i++) tmp[i] = 1;
        append_store(one, tmp);
        for (int i = 0; i < n; i++) {
            append_add(sum, sum, one),
            append_right(qaq, sum, 1999); // 有多少个 1 就有多少个 0
            append_left(r, r, 1),
            append_add(r, r, qaq);
        }
        append_not(r, r);
        return;
    }
​
    init(2);
    for (int d = 0; d < n; d++) {
        // get r0, get r1
        int ta1 = 13;
        if (d & 1) {
            append_and(ta1, r, LOW);
            append_right(r, r, k);
            append_or(r, r, HIH);
        }
        append_and(r0, r, getr0);
        append_right(r1, r, k);
        append_and(r1, r1, getr0);
​
        // get r0mr1
        getneg(r0mr1, r1);
        append_add(r0mr1, r0, r0mr1);
​
        // get w
        append_right(w, r0mr1, k);
        append_and(w, w, add1);
​
        // get tw : > -> 0, < -> 1
        int tw = 6, revtw = 7;
        getneg(tw, w);
        append_and(tw, tw, neg); // 清洗 k + 1
        append_xor(revtw, tw, neg);
​
        // get new r
        int sr0 = 10, sr1 = 11, ans = 12;
        append_and(sr0, r0, tw); append_and(sr1, r1, revtw);
        append_add(ans, sr0, sr1); // ans = min
        append_and(sr0, r0, revtw); append_and(sr1, r1, tw);
        append_add(r1, sr0, sr1); // r1 = max
        append_left(r1, r1, k);
        append_add(r, ans, r1);
​
        if (d & 1) {
            append_left(r, r, k);
            append_or(r, r, ta1);
        }
    }
}
}
​
void construct_instructions(int subtask, int n_, int k_, int q_) {
    n = n_, k = k_;
    if (subtask == 0) SUBTASK0::solve();
    else SUBTASK1::solve();
}
​