P8264

卡到最优解了，这不得写写。顺便讲点实现上的细节。

看起来不会 polylog，观察到是 ynoi 题且 $n\le 10^5$，于是考虑分块。

一个很简单的想法是，如果对于每块能预处理出 $f_{i,j}$ 表示第 $i$ 块，一开始 $v=j$，经过块内的所有变换会变成 $f_{i,j}$。考虑怎么对于每个块 $O(n)$ 预处理。

容易发现，对于每次操作 $v=|a_i-v|$，对于 $v=a_i+1$ 和 $v=a_i-1$，进行完这次操作后两者都会变成 $1$，其他以此类推。而变成这两者一样的后，以后的操作得到的结果也是一样的，于是可以使用并查集状物合并在一起。

此时发现，若可以保证每个数只被合并一次，就可以保证复杂度。怎么做呢？首先发现，任何时刻没有并到其它位置的数形如一个区间 $[l,r]$。若 $a_i\not\in [l,r]$ 则不做合并，否则，若 $a_i-l\le r-a_i$ 则把 $[l,a_i-1]$ 合并到另一侧，这样就能保证每做一次合并就减少一个剩下的数了。$a_i-l>r-a_i$ 类似。

于是发现现在要维护的操作就是全局乘上 $-1$，全局加某个数。打个 tag 解决。这样就预处理好了 $f$。散块则直接暴力。时间复杂度 $O(n\sqrt n)$。

感觉细节还是很多的。做合并的时候，最好的方法是先将当前剩下的区间 $[l,r]$ 转化成其真正对应的区间 $[tl,tr]$ 再合并。并且注意打完 tag 之后要立刻更新 $tl,tr$。

怎么卡到最优解呢？注意到我们询问的时候常数非常之小，于是可以预处理少一点东西，具体就是调块长，经测试调到 $B=1050$，加上快读快输能跑到 $9s$ 以内。

code：

int n,m=1e5,q,a[N];
struct DSU{
	int fa[N],c[N];
	void init(){
		rep(i,0,m){
			fa[i]=i,c[i]=i;
		}
	}
	int find(int x){
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	il void merge(int x,int y){
		fa[find(x)]=find(y);
		c[find(x)]=y;
	}
}D;
struct Block{
	int B,id[N],f[107][N];
	#define L(i) (((i)-1)*B+1)
	#define R(i) min((i)*B,n)
	void build(){
		B=1050;
		rep(i,1,n){
			id[i]=(i-1)/B+1;
		}
		rep(j,1,id[n]){
			D.init();
			int l=0,r=m,x=1,y=0;
			rep(i,L(j),R(j)){
				int tl=l*x+y,tr=r*x+y;
				if(tl>tr){
					swap(tl,tr);
				}
				if(a[i]-tl<=tr-a[i]){
					rep(k,tl,a[i]-1){
						D.merge((k-y)*x,(a[i]+a[i]-k-y)*x);
					}
					y-=a[i];
					tl=max(tl,a[i])-a[i],tr-=a[i];
				}else{
					rep(k,a[i]+1,tr){
						D.merge((k-y)*x,(a[i]+a[i]-k-y)*x);
					}
					x*=-1,y*=-1,y+=a[i];
					tl=a[i]-tl,tr=a[i]-min(tr,a[i]);
				}
				l=(tl-y)*x,r=(tr-y)*x;
				if(l>r){
					swap(l,r);
				}
			}
			rep(i,0,m){
				f[j][i]=x*D.c[D.find(i)]+y;
			}
		}
	}
	int query(int l,int r,int v){
		int x=id[l],y=id[r];
		if(x==y){
			rep(i,l,r){
				v=abs(v-a[i]);
			}
			return v;
		}
		rep(i,l,R(x)){
			v=abs(v-a[i]);
		}
		rep(i,x+1,y-1){
			v=f[i][v];
		}
		rep(i,L(y),r){
			v=abs(v-a[i]);
		}
		return v;
	}
}B;
void Yorushika(){
	read(n,q);
	rep(i,1,n){
		read(a[i]);
	}
	B.build();
	int lst=0;
	while(q--){
		int l,r,v;read(l,r,v);
		l^=lst,r^=lst,v^=lst;
		write(lst=B.query(l,r,v)),puts("");
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}