P10308 「Cfz Round 2」Osmanthus 题解

· · 题解

题目大意

一开始有一个序列 a，有 q 次修改，每次可以修改一个值。对于每次修改后你需要输出此时的 a 进行以下操作若干次的循环节最小长度：

题目分析

首先，我们发现，对于第 i 个元素，它会把前面的元素的组合都出现一遍，那么 a_i 肯定 2^{\lceil \log_2 i \rceil} 循环一次。对于长度为 n 的序列，循环节就是所有 a_i 循环节的最小公倍数，由于都是 2 的整数次方，所以为 2^{\lceil \log_2 n \rceil}。

但是很明显，有一段是特殊的，即 a 的前导 0，不管迭代其次也不会改变自身，不会影响后面的东西。

然后我们要维护动态前导 0，很多人暴力维护赛时过了，这里已经 hack 掉了（第 7 个点）。This。

其实这个动态前导 0 类似一个动态 \operatorname{mex}，可以用 set 维护。详见 Link 的 set 部分。

时间复杂度 \mathcal{O}(n\log n)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int a[maxn];
int main()
{
    int n,q;
    cin>>n>>q;
    set<int> s;
    for(int i=1;i<=n+1;i++)
    s.insert(i);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==0) s.erase(s.lower_bound(i));
    }
    while(q--)
    {
        int x,z;
        scanf("%d%d",&x,&z);
        if(a[x]!=0&&z==0) s.erase(s.lower_bound(x));
        else
        {
            if(a[x]==0&&z!=0)
            s.insert(x);
        }
        a[x]=z;
        int y=n-*s.begin()+1;
        int ans=1;
        while(ans<y) ans*=2;
        cout<<ans<<"\n";
    }
}