题解：P8264 [Ynoi Easy Round 2020] TEST_100

比较不一样的做法，不需要维护系数。
容易想到分块，但是预处理出来每个数经过块后的结果不是很好做。
可以直接平衡树，不知道为啥别的题解都要可持久平衡树，平衡树可以直接类似线段树一样

\mathcal{O}(n)

建树，或者也可以提前处理一份，每次复制也行。发现这道题的合并是有交的，平衡树有交合并为

\mathcal{O}(\log^2n)

的，但是这道题的节点合并一次后就消失了，所以总体复杂度还是

\mathcal{O}(n\log n)

的，上一篇题解这里复杂度分析的有问题。

但是上平衡树其实就没啥意思了，类似于 ARC149D 的思想，预处理出

[l,r]

的答案，时刻维护一个原点

k

与这个区间的相对关系，设给出的数为

x

，有如下情况：

原点在区间的右边，那么整个区间要左移，相当于原点右移， $k\gets k+x$ 。
原点在区间的左边，相当于区间翻转后右移了 $x$ ，相当于原点左移， $k\gets k-x$ 。

处理完之后，如果区间跨越了原点，就将短的一侧翻折过来即可，因为之后他们的答案都一样，这个可以用并查集实现。最后，距离原点的距离就是经过这个块后的答案，时间复杂度

\mathcal{O}(n\sqrt n)

。

CPP

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937_64 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
const int N=1e5+10,LEN=450;
int n,m,a[N],len,d[LEN][N],fa[N],ID[N],lastans;
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
signed main(){
    // freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();m=read();len=2*std::sqrt(n);for(int i=1;i<=n;++i)a[i]=read(),ID[i]=(i-1)/len+1;
    for(int i=1;i<=n/len+1;++i){
        int L=(i-1)*len+1,R=std::min(L+len-1,n),l=0,r=N-5,k=0;
        for(int i=l;i<=r;++i)fa[i]=i;
        for(int i=L;i<=R;++i){
            int x=a[i];
            if(k<=l)k+=x;else k-=x;
            if(l<k&&r>k){
                if(k-l<r-k){for(int i=l;i<k;++i)fa[i]=2*k-i;l=k;}
                else{for(int i=r;i>k;--i)fa[i]=2*k-i;r=k;}
            }
        }
        for(int j=0;j<=N-5;++j)d[i][j]=std::abs(k-find(j));
    }
    for(int i=1;i<=m;++i){
        int l=read()^lastans,r=read()^lastans,v=read()^lastans;
        int lid=ID[l],rid=ID[r];
        if(lid==rid)for(int i=l;i<=r;++i)v=std::abs(v-a[i]);
        else{
            for(int i=l;ID[i]==lid;++i)v=std::abs(v-a[i]);
            for(int i=lid+1;i<rid;++i)v=d[i][v];
            for(int i=(rid-1)*len+1;i<=r;++i)v=std::abs(v-a[i]);
        }std::cout<<(lastans=v)<<'\n';
    }
}

题解：P8264 [Ynoi Easy Round 2020] TEST_100

文章操作

相关推荐

评论

题解：P8264 [Ynoi Easy Round 2020] TEST_100