Codeforces Round 675 (Div. 2)

Codeforces Round 675 (Div. 2)

C

注意是删除连续一段,前面的删除办法是$\sum_{i=1}^{pre} i$,后面的删除的贡献是$\sum 10^i \times (suf-(suf-i)+1=\sum_{i=0}^{suf} (x+i)10^i$,注意边界即可。

D

行,竖建点,注意离散化,以及起点可以随意跳跃,终点不可以

E

考虑贪心

  • $s[i]\not ={s[i+1]}$,直接加上。
  • $s[i] ={s[i+1]}$,不等于很好抉择,相等的话,考虑$11223,33321,3333321$,决定是否添加因素是$ans[i+2]$是否具备第一个字符$>$第二个不同字符。这是可以传递的。$33321$显然符合。
  • 注意要传递的同时,如果发生第一个字符不等于第二个字符需要重新特判。

F

只会$O(kq\log n+ q\log^2n),k=66$,小质数暴力动态线段树或者$short$线段树。大质数只会出现一次,可以考虑区间不同数的主席树的做法。$\sum_l^r [last[i]<l] sum[i]$。