自动搬运

查看原文

来自洛谷，原作者为

	zhy12138 AFOed

搬运于2025-08-24 22:37:28，当前版本为作者最后更新于2022-07-22 09:10:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么题解没一个正解啊（全恼）

首先我们不难发现我们实际要维护的是一个绝对值的复合函数

直接维护的话段数是 $2^n$ 级别的，所以考虑用一些特殊的数据结构维护

考虑从后往前依次加入函数，假设目前已经维护了后 $n$ 个的复合函数，现在正在加入倒数第 $n+1$ 个函数 $f(x)=|x-v|$

那么不难发现当 $x$ 在 $0\sim v$ 中，$f(x)$ 是 $v\sim 0$

当 $x$ 在 $v+1 \sim 10^7$ 中，$f(x)$ 是 $1 \sim 10^7-v$

因为我们已经维护好了后 $n$ 个的复合函数，那么我们只需要拿出这个复合函数的 $0 \sim v,1 \sim 10^7-v$ 两段，然后将前一段反转再拼接即可

不难发现这个操作可以用可持久化平衡树维护

然后因为需要支持区间查询，所以我们需要实现的是线段树套平衡树

这样查询时只需要在 $O(\log n)$ 个节点中花费 $O(\log V)$ 的复杂度找到对应的段，然后求值即可，复杂度 $O(m\log n\log V)$

而初始化时一共会进行 $O(n\log n)$ 次在前面加函数的操作，每次操作的复杂度是 $O(\log V)$

因此总复杂度为 $O((n+m)\log n\log V)$

但是我的实现空间常数很大（也可能是我写的可持久化 fhq_treap 复杂度有问题）

因此还要加两个小优化

第一个是线段树顶层不要二分，而是分为 $O(\log n)$ 个块

这样这一层最多在单次查询中多贡献 $O(\log n)$ 次节点查询，不改变复杂度

但是这一部分加入函数的次数就由 $O(n\log \log n)$ 变为 $O(n)$ 了

第二个是线段树底层不要到区间长度为 $1$ 再停，而是到 $O(\log n\log V)$ 就停，查询的时候就暴力扫过去

因为底层只会有 $O(1)$ 个节点被查询，因此复杂度不变，且显然少加了很多次函数

代码实现比较傻，仅供参考

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<vector>
#include<random>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
const int inf=1e5;
int read()
{
	int kkk=0,x=1;
	char c=getchar();
	while((c<'0' || c>'9') && c!='-') c=getchar();
	if(c=='-') c=getchar(),x=-1;
	while(c>='0' && c<='9') kkk=kkk*10+(c-'0'),c=getchar();
	return kkk*x;
}
int n,m,a[MAXN],ans;
mt19937 gen(time(NULL));
int root[MAXN*2],rcnt,pcnt;
vector<int> son[MAXN*2];
struct fhq_treap
{
	int ly,ry;
	int size;
	int slen;
	int l,r;
	bool tag;
}tree[MAXN*600];
#define ls(x) (tree[x].l)
#define rs(x) (tree[x].r)
void up(int x)
{
	tree[x].size=tree[ls(x)].size+tree[rs(x)].size+1;
	tree[x].slen=tree[ls(x)].slen+tree[rs(x)].slen+abs(tree[x].ly-tree[x].ry)+1;
}
int copy(int x)
{
	int bck=++pcnt;
	tree[bck]=tree[x];
	return bck;
}
int check(int x,int y)
{
	uniform_int_distribution<int> dcd(1,tree[x].size+tree[y].size);
	return dcd(gen)<=tree[x].size;
}
int calc(int o,int len)
{
	if(len==1) return tree[o].ly;
	else return tree[o].ly+(len-1)*(tree[o].ly>tree[o].ry?-1:1);
}
int NEW(int ly,int ry)
{
	int bck=++pcnt;
	tree[bck].ly=ly;
	tree[bck].ry=ry;
	tree[bck].slen=abs(ly-ry)+1;
	tree[bck].size=1;
	return bck;
}
void turn(int x)
{
	tree[x].tag^=1;
	swap(ls(x),rs(x));
	swap(tree[x].ly,tree[x].ry);
}
void down(int x)
{
	if(!tree[x].tag) return;
	if(ls(x)) tree[x].l=copy(ls(x)),turn(ls(x));
	if(rs(x)) tree[x].r=copy(rs(x)),turn(rs(x));
	tree[x].tag=0;
}
int merge(int x,int y)
{
	if(!x || !y) return x+y;
	int bck;
	if(check(x,y))
	{
		bck=copy(x); down(bck);
		tree[bck].r=merge(rs(bck),y);
	}
	else
	{
		bck=copy(y); down(bck);
		tree[bck].l=merge(x,ls(bck));
	}
	up(bck);
	return bck;
}
void split_len(int x,int len,int &lx,int &rx)
{
	if(!x) {lx=rx=0;return;}
	if(tree[ls(x)].slen+abs(tree[x].ly-tree[x].ry)+1<=len)
	{
		lx=copy(x); down(lx);
		split_len(rs(lx),len-tree[ls(x)].slen-(abs(tree[x].ly-tree[x].ry)+1),rs(lx),rx);
		up(lx);
	}
	else
	{
		rx=copy(x); down(rx);
		split_len(ls(rx),len,lx,ls(rx));
		up(rx);
	}
}
void split_size(int x,int size,int &lx,int &rx)
{
	if(!x) {lx=rx=0;return;}
	if(tree[ls(x)].size+1<=size)
	{
		lx=copy(x); down(lx);
		split_size(rs(lx),size-tree[ls(x)].size-1,rs(lx),rx);
		up(lx);
	}
	else
	{
		rx=copy(x); down(rx);
		split_size(ls(rx),size,lx,ls(rx));
		up(rx);
	}
}
int find(int &x,int &len,int &S)
{
	if(tree[x].tag) x=copy(x),down(x);
	if(tree[ls(x)].slen>=len) return find(ls(x),len,S);
	else
	{
		S+=tree[ls(x)].size;
		len-=tree[ls(x)].slen;
		if(abs(tree[x].ly-tree[x].ry)+1>=len) return x;
		else
		{
			++S;
			len-=abs(tree[x].ly-tree[x].ry)+1;
			return find(rs(x),len,S);
		}
	}
}
void get_split_len(int &x,int len,int &lx,int &rx)
{
	int tmp=len,S=1;
	int o=find(x,tmp,S);
	if(abs(tree[o].ly-tree[o].ry)+1!=tmp)
	{
		int A,B,C,F;
		split_size(x,S,F,C);
		split_size(F,S-1,A,B);
		int D=NEW(tree[o].ly,calc(o,tmp));
		int E=NEW(calc(o,tmp+1),tree[o].ry);
		lx=merge(A,D);
		rx=merge(E,C);
	}
	else split_len(x,len,lx,rx);
}
void init(int l,int r,int x)
{
	for(int i=r;i>=l;--i)
	{
		int A,B,C,D;
		get_split_len(root[x],a[i]+1,A,B);
		get_split_len(root[x],inf-a[i]+1,C,B);
		get_split_len(C,1,B,D);
		turn(A);
		root[x]=merge(A,D);
	}
}
const int base=2000;
void build(int l,int r,int &x)
{
	x=++rcnt;
	if(r-l<=1000) return;
	if(x==1)
	{
		int N=(n-1)/base+1;
		son[x].resize(N);
		for(int i=1;i<=N;++i)
		{
			build((i-1)*base+1,min(n,i*base),son[x][i-1]);
		}
		root[x]=NEW(0,inf);
		init(l,r,x);
		return;
	}
	int mid=(l+r)>>1;
	son[x].resize(2);
	build(l,mid,son[x][0]);
	build(mid+1,r,son[x][1]);
	if(root[son[x][1]])
	{
		root[x]=copy(root[son[x][1]]);
		init(l,mid,x);
	}
	else
	{
		root[x]=NEW(0,inf);
		init(l,r,x);
	}
}
int cx(int l,int r,int L,int R,int v,int x)
{
	if(r-l<=1000)
	{
		for(int i=max(L,l);i<=min(R,r);++i) v=abs(v-a[i]);
		return v;
	}
	if(L<=l && r<=R)
	{
		++v;
		int S=0;
		int o=find(root[x],v,S);
		return calc(o,v);
	}
	if(x==1)
	{
		int N=(n-1)/base+1;
		int bck=v;
		for(int i=1;i<=N;++i)
		{
			if(max((i-1)*base+1,L)<=min(min(n,i*base),R)) bck=cx((i-1)*base+1,min(n,i*base),L,R,bck,son[x][i-1]);
		}
		return bck;
	}
	int mid=(l+r)>>1;
	if(R<=mid) return cx(l,mid,L,R,v,son[x][0]);
	if(mid<L) return cx(mid+1,r,L,R,v,son[x][1]);
	return cx(mid+1,r,L,R,cx(l,mid,L,R,v,son[x][0]),son[x][1]);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	int R;
	build(1,n,R);
	while(m--)
	{
		int l=read()^ans,r=read()^ans,v=read()^ans;
		printf("%d\n",ans=cx(1,n,l,r,v,R));
	}
	return 0;
}
//tetu no isi to hagane no tuyosa