由于本人不是这场的出题人，题解和标算可能不一致。
Igra
关键字：贪心
记 $A,B$ 分别为Alice和Bob的串。问题等价于将 $a$ 个 $\mathrm{a}$，$b$ 个 $\mathrm{b}$，$c$ 个 $\mathrm{c}$ 填入串 $A$，使得 $A[i]=B[i]$ 恒成立。
由于数据保证有解，考虑这样一种思路：从左往右贪心确定 $A$ 的每个字符的最小值。
依次对于 $i=1,2,\cdots,n$，枚举最小的 $A[i]$，要求这样的 $A[i]$ 能使问题有解（注意 $A[1,i-1]$ 已经确定）。用 $a,b,c$ 分别表示字母 $\mathrm{a},\mathrm{b},\mathrm{c}$ 的剩余个数，不妨以 $A[i]=\mathrm{a}$ 为例，则需要满足的条件是：
- $a > 0$ 且 $B[i]\ne\mathrm{a}$；
- 可以将 $a-1$ 个 $\mathrm{a}$，$b$ 个 $\mathrm{b}$，$c$ 个 $\mathrm{c}$ 填入 $A[i+1,n]$，使得 $A[j]\ne B[j]$ 恒成立。
如果前者不成立，那么显然 $A[i]=\mathrm{a}$ 不可行。现在我们假设前者成立，关键在于判定后者是否成立。先把 $a$ 减掉 $1$，并且设 $B[i+1,n]$ 中，$\mathrm{a},\mathrm{b},\mathrm{c}$ 出现的个数分别 $a',b',c'$（显然 $a'+b'+c'=a+b+c$），$f(\alpha,\beta)$ 表示 $A$ 中字母 $\alpha$ 有多少个被放在了 $B$ 中字母为 $\beta$ 的位置（即满足 $A[j]=\alpha,B[j]=\beta$ 的位置 $j$ 的个数），则有：
--------+-------------+-------------+-------------
f(α,β) | β="a" | β="b" | β="c"
--------+-------------+-------------+-------------
α="a" | 0 | (1) | (2) (1)+(2)=a
--------+-------------+-------------+-------------
α="b" | (3) | 0 | (4) (3)+(4)=b
--------+-------------+-------------+-------------
α="c" | (5) | (6) | 0 (5)+(6)=c
--------+-------------+-------------+-------------
(3)+(5)=a' (1)+(6)=b' (2)+(4)=c'设 (1) 为 $x$，可以推出
--------+-------------+-------------+-------------
f(α,β) | β="a" | β="b" | β="c"
--------+-------------+-------------+-------------
α="a" | 0 | x | a-x
--------+-------------+-------------+-------------
α="b" | b-c'+a-x | 0 | c'-a+x
--------+-------------+-------------+-------------
α="c" | a'-b+c'-a+x |c-a'+b-c'+a-x| 0
--------+-------------+-------------+-------------$A[i]=\mathrm{a}$ 有解的条件是存在一个整数 $x$，使得表中每个数均非负，即
$$x\ge\max\{0,a-c',a-c'+b-a'\}$$ $$x\le\min\{a,a-c'+b,a-c'+b-a'+c\}$$
因此当 $\max\{0,a-c',a-c'+b-a'\}\le\min\{a,a-c'+b,a-c'+b-a'+c\}$ 时，说明确定 $A[i]=\mathrm{a}$ 可行。反之，$A[i]=\mathrm{a}$ 不可行，就继续枚举 $A[i]=\mathrm{b}$ 和 $A[i]=\mathrm{c}$ 判断是否可行。
这样就可以确定有解时最小的 $A[i]$。依次对于 $i=1,2,\cdots,n$ 确定最小的 $A[i]$，最后的串 $A$ 就是答案。
时间复杂度 $O(n)$。
Sirni
关键词：最小生成树，优化建图
看完题目，我们首先可以想到一种做法，即把整个完全图建出来，然后用Prim或Kruskal算法求其最小生成树。这样做的复杂度为 $O(n^2)$（使用Prim）或 $O(n^2\log n)$（使用Kruskal），可以得到30分。
这个做法的瓶颈在于边数过多，为 $O(n^2)$ 级别，难以承受 $n=10^5$ 的数据。不过我们其实可以注意到，有很多边是没有用的。
首先有一个明显的性质：点权相同的点只要留一个。因为，如果 $p_i=p_j$，那么点 $i,j$ 间连边不需要代价，显然可以直接连起来，并且把和 $p_j$ 关联的边 $(p_j,v)$ 改成 $(p_i,v)$，代价不变；因此可以直接删掉 $p_j$。
现在的 $p_i$ 两两不同。考虑边 $(u,v)$ 的权值，其中 $u < v$，则权值 $w=\min\{u,v\bmod u\}=v\bmod u$。我们观察当 $u$ 一定，$v$ 增大时权值 $w$ 的变化，发现 $w$ 被分成了若干段 $[u+1,2u),[2u,3u),[3u,4u)\cdots$，每段的 $w$ 是一个公差为1的等差数列：
v u+1 u+2 ... 2u-1 2u 2u+1 2u+2 ... 3u-1 3u 3u+1 3u+2 ...
w 1 2 ... u-1 0 1 2 ... u-1 0 1 2 ...对于每一段 $[ku+[k=1],(k+1)u)$（$k$ 为正整数），可能有多个点的权值落在该区间内，我们可以只保留 $u$ 连到该区间内权值最小的点的边。
为什么呢？
设该区间内有两个点，权值为 $p,q$，且 $p < q$，则边 $(u,p)$ 的权为 $p-ku$，$(u,q)$ 的权为 $q-ku$，$(p,q)$ 的权为 $q\bmod p$。因为 $q > p$，所以 $q\bmod p\le q-p$。这说明
$$q-ku=(p-ku)+(q-p)\ge(p-ku)+(q\bmod p)$$
也就是说，连边 $(u,q)$ 不如连边 $(u,p),(p,q)$，虽然后者连了两条边，但代价不可能比前者大！
这就证明了往该段中不是最小的点连边不优。去掉这种不优的边以后，剩下的边有多少呢？对于点 $i$，满足 $v > p_i$ 的边 $(p_i,v)$ 最多有 $\min\{{10^7\over p_i},n\}$ 条，所以当 $n=10^5$ 时，边数 $m$ 满足
$$m\le\sum_{i=1}^n\min\{{10^7\over i},n\} < 8\times 10^7$$
现在的边数可以接受了，我们也就能得到大致算法：
- 去掉相同的 $p_i$；
- 对每个点 $i$ 和每个正整数 $k$，如果存在点 $j$ 满足 $kp_i+[k=1]\le p_j < (k+1)p_i$，那么取 $p_j$ 最小的一个，连边 $(p_i,p_j)$；
- 用Kruskal算法求图的最小生成树。
当然程序还需要精细地实现，否则仍然会超时。实现中需要优化的是2、3两个步骤。
- 第2步的连边复杂度可以优化到 $O(n+m)$（$m$ 为边数），方法是预处理大小为 $10^7$ 的数组 $f[x]$ 表示大于等于 $x$ 的最小点权对应的点，这样就可以 $O(1)$ 找出下一个 $k$：
for(int i = 1; i <= n; i++) f[p[i]] = i;
for(int i = 1e7; i; i--) if(!f[i]) f[i] = f[i + 1];- 第3步的Kruskal，如果一开始用 $O(m\log m)$ 时间给边排序，容易超时；不过注意到边权只有 $10^7$ 种，不妨开 $10^7$ 个边表（编号 $0$ 到 $10^7-1$）存每种权的边，加边时按权值加入对应边表，最后按顺序遍历边表就是排好序的了。
这样就可以在5s时限内出解，得到100分了。
Poklon
关键词：问题转化，树状数组
下面记给定的数列为 $a_1,a_2,\cdots,a_n$。
不难设计出这样的暴力算法：对于每次询问 $l,r$，用 $O(n)$ 的时间统计 $a_l,a_{l+1},\cdots,a_{r-1},a_r$ 中出现两次的数的个数。怎样统计呢？开一个数组统计每个数出现的次数。然而数值范围是 $[0,10^9]$，这么大的数组开不下，怎么办？
将 $a$ 从小到大排序，得到下标序列 $b$，则 $a_{b_1}\le a_{b_2}\le\cdots\le a_{b_n}$。然后将 $a$ 中最小的数改成 $1$，第二小的数改成 $2$，第三小的数改成 $3$……例如序列 $a=[2,7,1,8,2,8]$ 修改的过程如下：
i 1 2 3 4 5 6
b[i] 3 1 5 2 4 6
修改前 a[b[i]] 1 2 2 7 8 8
修改后 a[b[i]] 1 2 2 3 4 4
修改前 a[i] 2 7 1 8 2 8
修改后 a[i] 2 3 1 4 2 4显然相同的数改完以后仍然相同，不同的数改完以后仍然不同，所以不影响答案。并且现在的数值范围是 $[1,n]$，询问时，可以直接开大小为 $n$ 的数组统计每个数的出现次数了。对于每个询问 $l,r$，实现如下：
- 开一个大小为 $n$，初值为 $0$ 的数组 $t$，初始答案 $s=0$；
- 依次对于 $i=l,l+1,\cdots,r-1,r$，将 $t[a_i]$ 增加 $1$：
- 如果增加后 $t[a_i]=2$，则令 $s$ 增加 $1$；
- 如果增加后 $t[a_i]=3$，则令 $s$ 减少 $1$；
- 其余情况 $s$ 不变。
- 最后 $s$ 的值就是 $t$ 中 $2$ 的个数，即答案。
直接实现的复杂度为 $O(Qn)$，可以获得40分。
要得到更高的分数，则需要进一步观察该过程。假设我们一边做这个过程时一边在序列上做标记，把 $t[a_i]$ 的值标记在 $i$ 位置上，那么该询问的答案就是区间内2标记的个数减去3标记的个数。
形式化地，定义长度为 $n$ 的序列 $c$，当 $i$ 位置为2标记时，$c_i=1$，当 $i$ 位置为3标记时，$c_i=-1$，否则 $c_i=0$，那么该询问的答案为
$$\sum_{i=1}^rc_i$$
但问题还没有解决！不同的询问 $l$ 可以不同，即序列 $c$ 可能不同。考虑这样一件事情：一开始序列 $a$ 为空，每次在 $a$ 的左端加入一个数，维护此时的序列 $c$。下面是 $a=[3,2,2,3,2,3,2]$ 的例子：
a: 2
c: 0 0 0 0 0 0 0
a: 3 2
c: 0 0 0 0 0 0 0
a: 2 3 2
c: 0 0 0 0 0 0 [1]
a: 3 2 3 2
c: 0 0 0 0 0 [1] 1
a: 2 3 2 3 2
c: 0 0 0 0 [1] 1[-1]
a: 2 2 3 2 3 2
c: 0 0 [1] 0[-1] 1 [0]
a: 3 2 2 3 2 3 2
c: 0 0 1 [1]-1[-1] 0每次加入一个数，$c$ 序列的修改已用 [] 标识，可以发现加入 $a_i$ 时，$c$ 至多有三项发生改变：$a_i$ 的第 $2$ 次出现处 $c$ 由 $0$ 变 $1$（如果有），$a_i$ 的第 $3$ 次出现处 $c$ 由 $1$ 变 $-1$（如果有），$a_i$ 的第 $4$ 次出现处 $c$ 由 $-1$ 变 $0$（如果有）。这里的第几次出现指的都是以 $i$ 为左端点。
算法过程如下：
- 将询问按照 $l$ 分类（可以直接按 $l$ 排序，也可以开 $n$ 个链表存每种 $l$ 的询问）；
- 假设一开始序列 $a$ 为空，依次对于 $l=n,n-1,\cdots,2,1$：
- 在序列 $a$ 中加入 $a_i$，并更新序列 $c$ 位于 $a_i$ 的第 $2,3,4$ 次出现处的值（如果有）；
- 处理以 $l$ 为左端点的所有询问：询问 $(l,r)$ 的答案为 $\sum_{i=1}^rc_i$。
查询 $a_i$ 的第 $2,3,4$ 次出现处的值，实际上只要处理出 $a_i$ 的下一次出现位置 $\mathrm{next}[i]$ 即可解决。至于 $\mathrm{next}[i]$ 数组如何处理，同样可以将 $a$ 从小到大排序，相同的 $a_i$ 按下标 $i$ 从小到大排序，得到下标序列 $b$，那么当 $a_{b_i}=a_{b_{i+1}}$ 时，$\mathrm{next}[b_i]=b_{i+1}$，否则 $\mathrm{next}[b_i]$ 不存在。
最后，查询 $\sum_{i=1}^rc_i$ 的复杂度仍然是 $O(n)$ 的，因此我们要用树状数组维护 $c$ 将复杂度优化到 $O(\log n)$：
int T[MaxN]; // 初始值为 0 的树状数组
void add(int i, int x) { // 将 c[i] 增加 x
for(; i <= n; i += i&-i) T[i] += x;
}
int sum(int i) { // 查询 c[1]+c[2]+...+c[i]
int s = 0;
for(; i; i -= i&-i) s += T[i];
return s;
}那么加入 $a_i$ 时，更新 $c$ 的过程如下（假设不存在的 next[i] 值为 n+1，且 next[n+1]=n+1）：
add(next[i],1);
add(next[next[i]],-2);
add(next[next[next[i]]],1);询问 $l,r$ 的答案，用 sum(r) 即可。
最后这个问题就完美解决了，时间复杂度 $O((n+Q)\log n)$，可以获得100分。
