A. Fence
输出(a+b+c-1)即可.
B. Nice Matrix
找到某些必须相等的四元组或者二元组,将它们变成当中第二大的数.
C. Bargain
统计每位的贡献,考虑从左到右第(i)位,该为数字为(d).
如果去掉的区间在该位前,则贡献为(dfrac12di(i-1)10^{n-i});
如果去掉的区间在该位后,则贡献为(ddisplaystylesum_{j=1}^{n-i}j10^{j-1}).
复杂度(O(log n)).
D. Returning Home
可能的方案只有两种:
1.直接从起点到终点;
2.从起点出发(经过零个或多个特殊点)到某个特殊点后再到终点.
因此只要求出起点到每个特殊点的最短路即可求出答案.
对横纵坐标建图,有三种边:
1.起点到坐标连边;
2.特殊点横纵坐标间连权为零的边;
3.相邻横纵坐标连边.
复杂度(O(mlog m)).
E. Minlexes
从后往前添加字符贪心,每次去掉相邻字符当且仅当满足条件并且连续一段相同字符后没有字符或者字符更小.
复杂度(O(|s|)).
F. Boring Queries
考虑离线版本.
从左往右枚举右端点,维护关于左端点的答案.具体地,使用支持单点修改和区间乘法询问的线段树,维护一个数组(b)使得(b)中区间的积恰好是(a)中对应区间的最小公倍数.
每次右端点添加数(a={p_1}^{r_1}cdots {p_k}^{r_k}),需要去掉前面出现过某些相同的(p)的影响,再在该点赋值(a).
对每个质数使用栈记录当前关于该质数的贡献在哪些位置.
时间复杂度为(O((nlog a_max+q)log n)).
在线版本,使用可持久化线段树即可.