Description

Solution

维护区间修改和区间质数个数，观察发现 $0\le x\le 100\; \backslash leq\; x\; \backslash leq\; 10$，区间操作是每个数字乘上当前下标的 $xx$ 次方。

考虑先把原来的判断是否为质数，然后分类讨论：

• $x=0x\; =\; 0$，所有数字乘上 $11$， 结果不改变
• 下标为质数，当前 $a_i=1,x=1a\_i\; =\; 1,\; x\; =\; 1$, 那么乘上后改数字变为质数
• 剩下的操作都是让区间的数字变成非质数，做区间赋值为 $00$ 即可

使用一颗线段树维护质数个数和值为 $11$ 的个数

• 如果当前区间里没有 $11$，直接打 $tagtag$, 时间复杂度 $O(lo{g}_{2}n)O(log\_2n)$;
• 如果当前区间里有 $11$, 继续往下找，最多会执行 $nn$ 次找到叶子节点，这部分的复杂度是 $O(nlo{g}_{2}n)O(nlog\_2n)$, 剩余的每次复杂度是 $O(lo{g}_{2}n)O(log\_2n)$

所以分析得到，$mm$ 次操作下复杂度是 $O(nlo{g}_{2}n+mlo{g}_{2}n)O(nlog\_2n\; +\; mlog\_2n)$。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49408617&returnHomeType=1&uid=105308122