区间中的不动点

花神游历各国

题目链接:https://www.luogu.com.cn/problem/P4145

题意:给定一个序列,每次操作将一段指定的区间中每一个数开方后取整,或者求一段区间的和.数据范围$n,m \leq 1e5 \quad a_i\leq1e12$.

解析:很明显不能直接暴力,应该考虑区间数据结构来维护.而开方不能合并计算,打tag延迟计算的方式并不适用.

观察开方运算,发现即使最大的数,$1e12$,在6次开方计算后也会变成1,且值为1的数在开方运算中不再改变.其实本质上就是这个开方后取整运算构成的群都会回归到1这个不动点.如果一段连续的区间都为1,那么这个区间在后续的操作中都不再改变.

可以利用这个性质,维护区间是否全部都是不动点,如果已经都是了就不用再下放修改了.每个点最多修改6次,最后总复杂度仍然是$O(mlogn)$.

The Child and Sequence

题目链接:https://codeforces.com/problemset/problem/438/D

题意:给定一个序列,每次操作将一段指定的区间对给定的模数取模,或者求一段区间的和.数据范围$n,m \leq 1e5 \quad a_i\leq1e9$.

解析:很明显,取模运算也没有区间可并性,只能从运算本身的特点入手.

一个数在取模后,得到的结果一定小于他的二分之一.证明涉及数论.不过可以感性理解一下,如果模数小于二分之一,得到的结果一定小于模数；如果模数大于二分之一,那么结果等于原数减模数,仍然小于二分之一.

每次以二分之一的程度减少,有效操作的次数就是$logx$.对于这个$a_i\leq1e9$的范围足够了.

那么我们可以维护区间最大值,如果模数大于最大值,没有必要操作,直接return,否则下放计算后重新统计最大值.总复杂度$O(mlognloga_i)$

鸡格线

题目链接:https://ac.nowcoder.com/acm/contest/46800/G

题意:给定一个序列,每次操作将一段指定的区间中的每个数做$f(x)=round(10\sqrt x)$的变换k次,其中round为四舍五入函数,或者所有数的和.数据范围$n,m \leq 1e5 \quad a_i\leq1e9$.

解析:这个及格线算法看起来就是一个升级版的开方,不过还有一些不同之处.

普通的开方运算中,不动点只有0和1.而这个运算中看似只有0和100,但是打表可以发现,99也是不动点.$f(99)=round(10\sqrt 99) \simeq round(99.4987)=99$.大于100的数会回归100,而小于99的数会回归99.线段树的tag维护子区间的叶子结点是否满足任意一个不动点.

对于$a_i\leq1e9$的范围,最多10次就可以回归到100的不动点,总复杂度$O(mlogn)$.不过需要注意最好直接在叶子结点做k次运算,不然二分下放次数过多可能会被卡常.

void mdf(int p,int l,int r,int ql,int qr){
    if(sg[p]) return ;
    if(l==r){
        sum-=ar[l];
        for(int i=1;i<=k;++i){
            ar[l]=round(10.0*sqrt(ar[l]*1.0));
            if(ar[l]==100||ar[l]==0||ar[l]==99)break;
        }
        if(ar[l]==100||ar[l]==0||ar[l]==99)sg[p]=1;
        sum+=ar[l];
        return ;
    }
    if(ql<=mid) mdf(ls,l,mid,ql,qr);
    if(qr>mid) mdf(rs,mid+1,r,ql,qr);
    sg[p]=(sg[ls]&sg[rs]);
}