【YNOI2012】D2T1

一道分明就是数学题的$YNOI$题。

看到$v$这么小,觉得大不对。然后看着操作$1$,你会突然想起一个熟知的结论(?):区间长度大于$\lceil log_2v\rceil$肯定无解。证明应该也是较为容易的,你假设当前区间有$a_1,a_2,…,a_k$这么些数(区间长度不一定为$k$),那么若当前区间无解说明剩下的数不存在$a_1,a_2,…,a_k,a_1+a_2,|a_1-a_2|,…$之类的,这样一共有$3^k$个数。去掉相同的,可以证明有一个上界是$2^k-1$。你构造$2^0,2^1,…,2^{k-1}$,这样正好能表示$2^0$到$2^k-1$的所有数,首先证明了存在性。另一方面,你假设其中有一个数不是$2^m$,就假定$2^{k-1}$没有,变成$A$。那么$2^0$到$2^{k-1}-1$还是完全能表示,若$A>2^{k-1}$,则又会多出$2^{k-1}-1+1=2^{k-1}$个数,于是还是$2^k-1$。若$A\leq 2^{k-1}$,则只会变少不会变多。于是乎,按照上述归纳一下,就可以证明有一个上界是$2^k-1$(大概?)。所以就有了那个熟知的结论。

有了结论之后,剩下来的区间都是小于等于$10$的了。你暴力$dfs$一下,若当前子集和出现过了,则说明有解(就算集合有交去掉交的部分还是相等的),于是就可以$2^{10}$的判断其余情况。

区间立方的话,你就在线段树上打个标记,$+1$表示有一次立方操作。询问的时候暴力递归线段树的那个区间到叶子,那么每个数要做的次数就知道了。由于$3^n$有点大,所以利用扩展欧拉定理,讨论一下就好了。至于判$3^p$与$phi(v)$的大小关系,取对数就可以了。

总复杂度是(假社$n,m$同阶)$O(n(logn(logn+logv)+2^{10}))$,轻松跑过去了。