专栏文章

题解：P8264 [Ynoi Easy Round 2020] TEST_100

zzzy_zzy
P8264题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min79w6i
此快照首次捕获于
2025/12/01 21:43
3 个月前
此快照最后确认于
2025/12/01 21:43
3 个月前
查看原文

前言

感觉这个并查集用得有点妙啊。

解法

套路的，先进行分块。以下我们默认块长为 BB。
考虑对每一个块预处理每一个数经过这个块后的数值变化量，直接暴力枚举复杂度显然错完了。但是有一个比较聪明的暴力是，我们发现一个块内的数可以把一个值域区间劈成两半，其中这两半内的数的数值变化量一样，可以继续递归处理，这样的话每一个块处理的复杂度就是 O(2B)O(2^B)，加上查询的总复杂度是 O(n2+n2BB)O(\frac{n^2+n2^B}{B})，当 B=log⁡nB=\log n 时，复杂度为 O(n2log⁡n)O(\frac{n^2}{\log n})，看着能过的样子，但实测最高只有九十二分。
我们接着刚才的思路想，发现劈成两半时，两边的数会有重复，具体来说，对于一段值域区间 [l,r][l,r]，将其从 xx 处劈开，不妨令 2x<l+r2x<l+r，那么 ∀a∈[l,x)\forall a\in[l,x)，在进行完这次劈开操作后，它的结果会与 2x−a2x-a 完全相同，于是可以将这些结果重复的数用并查集并起来，省流一下也就是将短的那一边并到长的那一边去，这样递归只要往一边走就行了，查询的时候询问一下当前值对应的根节点最后的值就就行了。
由于每个数最多被合并一次，且这里的并查集不太好按秩合并，所以时间复杂度是 O(n2log⁡nB+nB)O(\frac{n^2\log n}{B}+nB) 的，取 B=nlog⁡nB=\sqrt{n\log n} 时，复杂度平衡为 O(nnlog⁡n)O(n\sqrt{n\log n})，可以通过。

AC code

CPP
#include<bits/stdc++.h>
using namespace std;
int a[100010],ks[100010];
struct node{
    int l,r,fl,dir;
    int fa[100010];
    inline int find(int x){
        if(fa[x]==x)return x;
        return fa[x]=find(fa[x]);
    }
}fk[120];
int ask(int l,int r,int v){
    int ll=ks[l],rr=ks[r];
    if(ll==rr){
        for(int i=l;i<=r;i++)v=abs(v-a[i]);
        return v;
    }
    for(int i=l;i<=fk[ll].r;i++)v=abs(v-a[i]);
    for(int i=ll+1;i<rr;i++){
        v=fk[i].fl*fk[i].find(v)+fk[i].dir;
    }
    for(int i=fk[rr].l;i<=r;i++)v=abs(v-a[i]);
    return v;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int len=900,tot=0;
    for(int i=1;i<=n;i++){
        ks[i]=(i-1)/len+1;
        if((i-1)%len==0){
            fk[++tot].l=i;
        }
        if(i%len==0){
            fk[tot].r=i;
        }
    }
    fk[tot].r=n;
    for(int i=1;i<=tot;i++){
        int l=0,r=1e5,fl=1,dir=0;
        for(int j=l;j<=r;j++)fk[i].fa[j]=j;
        for(int j=fk[i].l;j<=fk[i].r;j++){
            if(fl==1){
                if(r+dir<a[j]){
                    fl=-fl,dir=a[j]-dir;
                }
                else if(l+dir>a[j]){
                    dir-=a[j];
                }
                else{
                    if(r+dir-a[j]<a[j]-l-dir){
                        for(int k=r+dir;k>a[j];k--){
                            int fx=fk[i].find(k-dir),fy=fk[i].find(2*a[j]-k-dir);
                            if(fx!=fy)fk[i].fa[fx]=fy;
                        }
                        r=a[j]-dir;
                        fl=-fl,dir=a[j]-dir;
                    }
                    else{
                        for(int k=l+dir;k<a[j];k++){
                            int fx=fk[i].find(k-dir),fy=fk[i].find(2*a[j]-k-dir);
                            if(fx!=fy)fk[i].fa[fx]=fy;
                        }
                        l=a[j]-dir;
                        dir-=a[j];
                    }
                }
            }
            else{
                if(-l+dir<a[j]){
                    fl=-fl,dir=a[j]-dir;
                }
                else if(-r+dir>a[j]){
                    dir-=a[j];
                }
                else{
                    if(-l+dir-a[j]<a[j]+r-dir){
                        for(int k=-l+dir;k>a[j];k--){
                            int fx=fk[i].find(dir-k),fy=fk[i].find(dir-2*a[j]+k);
                            if(fx!=fy)fk[i].fa[fx]=fy;
                        }
                        l=dir-a[j];
                        fl=-fl,dir=a[j]-dir;
                    }
                    else{
                        for(int k=-r+dir;k<a[j];k++){
                            int fx=fk[i].find(dir-k),fy=fk[i].find(dir-2*a[j]+k);
                            if(fx!=fy)fk[i].fa[fx]=fy;
                        }
                        r=dir-a[j];
                        dir-=a[j];
                    }
                }
            }
        }
        fk[i].fl=fl,fk[i].dir=dir;
    }
    int lst=0;
    while(m--){
        int l,r,v;
        cin>>l>>r>>v;
        l^=lst,r^=lst,v^=lst;
        cout<<(lst=ask(l,r,v))<<"\n";
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...