ACGO挑战赛#13题解
T1
思路
求出两个旅行者的位置再计算他们之间的距离即可。
参考代码
时间复杂度分析
循环，O(h×w)O(h\times w)O(h×w)。
T2
思路
考虑使用 std::map 模拟数组。
对于操作1，模拟即可，即 mp [x] ++。
对于操作2，如果当前 ccc 不够 mpxmp_xmpx ，则将 mpxmp_xmpx 减去 ccc，否则直接将当前的 xxx 提出 mpmpmp，即 if (c < mp [x]) mp [x] -= c;else mp.erase (x);。
对于操作3，用当前 mpmpmp 中的最大值减去最小值即可，即 cout << mp.rbegin () -> first - mp.begin () -> first << endl;。
参考代码
时间复杂度分析
访问 rbeginO(logn)O(\log n)O(logn)，其余 O(1)O(1)O(1)，最终 O(n+qlogn)O(n+q\log n)O(n+qlogn)。
T3
思路
考虑使用 std::vector 建图，再枚举从一个点相邻的点数量及哪些点进行枚举。
参考代码
时间复杂度分析
循环中访问了 mmm 次（即每条边），但 sort 是 mlogmm\log mmlogm 的，所以综合时间 O(n+mlogm)O(n+m\log m)O(n+mlogm)。
T4
思路
数学题。
设首项为 k(k≥0)k(k\ge0)k(k≥0)，共有 mmm 项，则序列为 k,k+1,k+2,…,k+mk,k+1,k+2,\ldots,k+mk,k+1,k+2,…,k+m，算术级数之和为 k×m+m(m+1)2k\times m+\frac{m(m+1)}2k×m+2m(m+1) ，设 q=k×m+m(m+1)2q=k\times m+\frac{m(m+1)}2q=k×m+2m(m+1) ，则若知道 mmm，可以通过 k=(q−m(m+1)2)÷mk=(q-\frac{m(m+1)}2)\div mk=(q−2m(m+1) )÷m 得到，发现若 k=0k=0k=0，则 qqq
大约为 m2m^2m2，则 m=2×106m=2\times10^6m=2×106 时 qqq 一定大于题目给定的 nnn，因此可以暴枚 mmm 算 (q−m(m+1)2) mod m(q-\frac{m(m+1)}2)\bmod m(q−2m(m+1) )modm 是否为0求当前的 mmm 满不满足要求。
另外，当 k=0k=0k=0 时，定有序列 1,2,3,…,m−11,2,3,\ldots,m-11,2,3,…,m−1 也满足要求；当 k=1k=1k=1 时，序列 0,1,2,…,m0,1,2,\ldots,m0,1,2,…,m 也一定满足要求（因为0的问题）。
当 k>1k>1k>1 时，定有数列 −(k−1),−(k−2),…,0,1,…,k−1,k,…,m-(k-1),-(k-2),\ldots,0,1,\ldots,k-1,k,\ldots,m−(k−1),−(k−2),…,0,1,…,k−1,k,…,m 也一定满足要求（因为正负数抵消）。
参考代码
时间复杂度分析
根据思路，时间复杂度为 O(2n)O(\sqrt{2n})O(2n )，省略 2\sqrt22 后为 O(n)O(\sqrt n)O(n )。
T5
思路 BY复仇者_ERIKA
预处理 resi,jres_{i,j}resi,j 表示 iii 开头 jjj 结尾的子串个数，这个东西倒着做一遍前缀和就行，然后考虑一次询问的答案就是 resa,bres_{a,b}resa,b ，再考虑修改会造成什么影响，不难发现就是减少修改前的字母，增加修改后的字母，于是对于所有26个字母，用线段树统计他前面有多少个，后面有多少个然后把贡献减掉，(注意如果 i=ji=ji=j 会多减一次，所以要再加回来)然后修改完的字母再做一次逆操作就行。
T6
思路
对于操作一，如果是全部赋值成0，就相当于取消前面的全部操作，那么可以通过记录有哪些位置被操作过的方式撤回。而如果是全部赋成 kkk 就再用个变量记录一下输出答案时需要加多少变化量。
操作2，3可以用数组模拟。
当然也存在线段树写法，就不贴了。
参考代码
时间复杂度分析
O(n+q)O(n+q)O(n+q)。
