P8264 [Ynoi Easy Round 2020] TEST_100 题解

Zi_Gao · 2023-12-09 17:07:01 · 题解

前言

来个无脑分块做法，不需要并查集。

正文

首先有一个结论，观察到绝对值函数 f_a\left(x\right)=\left|x-a\right| 关于 x=a 这条直线对称，并且题目要求对这样的函数进行复合得到 g\left(x\right)=f_{a_0}\left(f_{a_1}\left(\cdots f_{a_n}\left(x\right)\cdots\right)\right)，显然 g\left(x\right) 函数的对称性和 f_{a_n}\left(x\right) 的对称性一样。

现在给定了一个长度为 n 的数组 a，每次询问给定 l,r,x，求 f_{a_r}\left(f_{a_{r-1}}\left(\cdots f_{a_l}\left(x\right)\cdots\right)\right) 的值，记为 f_{l,r}\left(x\right)。考虑对 a 序列分块，自然想到处理出每个块区间的函数复合后的长度为 V 的完整映射。由于第一个结论，可以考虑这样一个处理过程来求出 x\in\left[l,r\right] 对于 f_{s,t}\left(x\right) 函数的映射，进行一个分类讨论：

当 s=t 时直接计算。
当 a_{s}\in \left[l,r\right] 再进行一个分类讨论
1. 当 a_s-l\geq r-a_s 时，递归处理 x\in\left[0,a_s-l\right] 的 f_{s+1,t}，得到 x\in\left[l,a_s\right] 的 f_{s,t}\left(x\right)=f_{s+1,t}\left(a_s-\left(x-l\right)\right)，然后根据对称轴填充另一部分 f_{s,t}\left(x\right)=f_{s,t}\left(2a_s-x\right)。
2. 反正同理。
否则，进行一个分类讨论：
1. 当 a_s\le l 时，递归处理 x\in\left[l-a_s,r-a_s\right] 的 f_{s+1,t}，得到 x\in\left[l,a_s\right] 的 f_{s,t}\left(x\right)=f_{s+1,t}\left(x-l\right)。
2. 反之同理。

这样处理每一个块只需要填 \mathcal{O}\left(V\right) 次，不会重复填，所以预处理时间复杂度是 \mathcal{O}\left(\frac{nV}{B}\right)，总的时间复杂度是 \mathcal{O}\left(\frac{nV}{B}+m\left(\frac{n}{B}+B\right)\right)，实测当 B=2\sqrt{n} 时最优。

代码

代码实现上可以用一个函数 solve(l,r,s,t) 表示需要解决 x\in\left[l,r\right] 的映射关系，并且把这个映射关系填到记录映射数组的 \left[s,t\right] 位置上去。注意当 l\ge r 时将值域区间翻转一下 l\leftarrow 2a_s-l,r\leftarrow 2a_s-r。

AC CODE

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

const int NNNN=100010;
const int MMMM=1010;
// const int NNNN=110;
// const int MMMM=110;
int V=NNNN-5;

int abss(int x){return x<0?-x:x;}

struct BA{
    int len,cnt,id[NNNN],arr[NNNN],F[MMMM][NNNN],L[MMMM],R[MMMM],tag[MMMM];

    void build(int n,int *data){
        register int i;
        len=std::sqrt(n)*3;
        cnt=n/len;
        if(n%len) ++cnt;
        for(i=1;i<=n;++i) arr[i]=data[i],id[i]=(i-1)/len+1;
        for(i=1;i<=cnt;++i) L[i]=(i-1)*len+1,R[i]=i*len,buildB(i);
        R[cnt]=n;
        return;
    }

    void solve(int l,int r,int s,int t,int id,int now,int end){
        register int i;
        if(s>t) s=arr[now]-s+arr[now],t=arr[now]-t+arr[now];  
        if(now==end){
            for(i=l;i<=r;++i)
                F[id][i]=abss(i-l+s-arr[now]);
            return;
        }
        if(s<arr[now]&&arr[now]<t){
            if(arr[now]-s>t-arr[now]){
                solve(l,l+arr[now]-s,arr[now]-s,0,id,now+1,end);
                for(i=l+arr[now]-s+1;i<=r;++i)
                    F[id][i]=F[id][(l+arr[now]-s)-(i-(l+arr[now]-s))];
            }else{
                solve(l+arr[now]-s,r,0,t-arr[now],id,now+1,end);
                for(i=l;i<l+arr[now]-s;++i)
                    F[id][i]=F[id][(l+arr[now]-s)+((l+arr[now]-s)-i)];
            }
        }else solve(l,r,abss(s-arr[now]),abss(t-arr[now]),id,now+1,end);
        return;
    }

    void buildB(int id){
        return solve(0,V,0,V,id,L[id],R[id]);
    }

    int query(int l,int r,int x){
        register int i;
        int begin=id[l],end=id[r];
        if(begin==end){
            for(i=l;i<=r;++i) x=abss(x-arr[i]);
            return x;
        }
        for(i=l;id[i]==begin;++i)
            x=abss(x-arr[i]);
        for(i=begin+1;i<end;++i)
            x=F[i][x];
        for(i=L[end];i<=r;++i)
            x=abss(x-arr[i]);
        return x;
    }
}ba;

int arr[100010];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    register int i,latans=0,l,r,x;
    int n=read();
    int q=read();
    for(i=1;i<=n;++i) arr[i]=read();
    ba.build(n,arr);

    for(i=0;i<q;++i){
        l=read()^latans;
        r=read()^latans;
        x=read()^latans;
        print(latans=ba.query(l,r,x)),putchar('\n');
    }

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}