题解：P8264 [Ynoi Easy Round 2020] TEST_100

· · 题解

考虑分块，假设我们有办法求出 mp_{i,x} 表示 x 经过 i 块的操作之后能变成的值，我们就可以在查询的时候暴力处理散块和整块。

考虑如何求出 mp_{i,x}，显然我们枚举每一块。

考虑题目的操作本质上是对所有 x\ge a_i 的减 a_i，对所有 x < a_i 的变成 a_i-x，即乘负一再加 a_i，可以全局打标记，设为 tag_1,tag_2。

假设当前的数的最小值为 mn，最大值为 mx，且当前遇到的数 x=\frac{a_i-tag_2}{tag_1}，若 mn\ge x 或 mx\le x 直接全局打标记，否则按照 mx-x 与 x-mn 大小分类。

用并查集维护上述过程即可。

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
inline int read(){
    char c=getchar();
    int f=1,ans=0;
    while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
    while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
    return ans*f;
}
const int N=1e5+10,B=500;
int n,m,a[N]; 
namespace dsu{
int f[N];
inline void init(){for (int i=0;i<N;i++) f[i]=i;}
int find(int x){if (f[x]==x) return x;return f[x]=find(f[x]);}
inline void add(int x,int y){f[find(x)]=find(y);}
}//dsu
int L[N],R[N],bl[N],mp[N/B+10][N];
inline void build(){
    int tot=n/B;if (n%B) tot++;
    for (int i=1;i<=tot;i++) L[i]=R[i-1]+1,R[i]=i*B;R[tot]=n;
    for (int i=1;i<=n;i++) bl[i]=(i-1)/B+1;
    for (int i=1;i<=tot;i++){
        dsu::init();
        int mn=0,mx=N-1,tag1=1,tag2=0;
        for (int j=L[i];j<=R[i];j++){
            int x=(a[j]-tag2)/tag1;
            if (mn>=x) tag1=1,tag2=-x;
            else if (mx<=x) tag1=-1,tag2=x;
            else if (mx-x>x-mn){
                for (int i=mn;i<=x;i++) dsu::add(i,2*x-i);
                mn=x,tag1=1,tag2=-x;
            }
            else{
                for (int i=x;i<=mx;i++) dsu::add(i,2*x-i);
                mx=x,tag1=-1,tag2=x;
            }
        }
        for (int j=0;j<N;j++){int x=dsu::find(j);mp[i][j]=tag1*x+tag2;}
    }
}
inline int ask(int l,int r,int x){
    if (bl[l]==bl[r]){for (int i=l;i<=r;i++) x=abs(x-a[i]);return x;}
    for (int i=l;i<=R[bl[l]];i++) x=abs(x-a[i]);
    for (int i=bl[l]+1;i<bl[r];i++) x=mp[i][x];
    for (int i=L[bl[r]];i<=r;i++) x=abs(x-a[i]);
    return x;
}
main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    build();
    int last=0;
    while(m--){
        int l=read()^last,r=read()^last,x=read()^last;
        printf("%lld\n",last=ask(l,r,x));
    }
    return 0;
}