自动搬运

查看原文

来自洛谷，原作者为

	阿丑 ArrTue

搬运于2025-08-24 22:32:56，当前版本为作者最后更新于2021-06-26 15:30:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

传送门，是划水时口胡的一道大水题

前置知识：

可持久化线段树。

题意：

• 给出一个长度为 $n$ 的数列 $a_i$。

• $m$ 次在线询问，每次询问求出 $\sum\limits_{i=l}^{r-1}|x-a_i|\times|x-a_{i+1}|$。

• $n,m\le3\times10^5$。

为了简洁，设 $f_{x,i}=|x-a_i|\times|x-a_{i+1}|$。

分析：

这题题面看起来就像线段树，但注意到对于每个 $x$，$f_{x,i}$ 都不相同，我们也开不下 $10^9$ 棵线段树，所以暂时并不行。（对于 $10\%$ 的 $x\le10$ 的数据，这一方法就非常可行）

不过离散化后，我们可能只需要开 $3\times10^5$ 棵树，这提示我们往可持久化线段树的方向思考。

根据绝对值的定义，有：

$$|x-a|=\begin{cases}x-a&x\ge a\\-x+a &x<a\end{cases} $$

那么：

$$f_{x,i}=\begin{cases}x^2-(a_i+a_{i+1})x+a_ia_{i+1}&x\ge\max(a_i,a_{i+1})\text{ 或 }x<\min(a_i,a_{i+1})\\-x^2+(a_i+a_{i+1})x-a_ia_{i+1}&\min(a_i,a_{i+1})\le x<\max(a_i,a_{i+1})\end{cases} $$

只要 $x$ 与 $a_i$，$a_{i+1}$ 的关系确定后，我们就可以选择上述式子来求出答案，而不需要确定 $x$ 的具体值。

具体地，假设 $f_{x,i}=bx^2+cx+d$，则有 $\sum f_{x,i}=x^2\sum b+x\sum c+\sum d$，可以用线段树维护 $\sum b$，$\sum c$ 和 $\sum d$，这样线段树就与 $x$ 的具体值无关了。

注意到当 $x$ 增大的过程中，$x$ 与 $a_i$ 的关系最多改变一次（从 $x\le a_i$ 到 $x>a_i$），并且总是当 $x$ 超过 $a_i$ 的时候，$f_{x,i}$，$f_{x,i-1}$ 会改变。因此对于每个 $a_i$ 建一棵线段树，并使用可持久化线段树维护这 $n$ 棵树。每次 $x$ 超过 $a_i$ 时，在上一棵树的基础上修改 $f_{x,i-1}$ 和 $f_{x,i}$，就可以解决问题了。

思路：

1. 对每一个 $a_i$ 开一棵线段树，并使用可持久化线段树维护。

2. 对每个查询二分查找应该查询哪一棵线段树，直接查询即可。

---

技巧不多，直接上代码。

#include <bits/stdc++.h>
#define rep(i, l, r) for(register int i=l; i<=r; ++i)
#define rrep(i, r, l) for(register int i=r; i>=l; --i)
#define lfor(i, x) for(int i=head[x]; i; i=nxt[i])
#define ll long long
using namespace std;
inline ll read() {
	ll ret=0, k=1; char c; do if((c=getchar())=='-') k=-1; while(c<'0' || c>'9');
	while(c>='0' && c<='9') ret=(ret<<1)+(ret<<3)+(c^48), c=getchar(); return k*ret;
}
const int mN=3e5+100, mS=42*mN, mod=1e9+7;
int n, m, a[mN];
int ork, rk[mN];
int oe, head[mN], ver[mN], nxt[mN];
inline void add(int x, int y) {nxt[++oe]=head[x], ver[oe]=y, head[x]=oe;}

namespace Segment_Tree {
#define lc tree[p].son[0]
#define rc tree[p].son[1]
	int on, rt[mN];
	struct node {int son[2]; int b, c, d;} tree[mS];	//b c d 就是题解中提到的三个系数 
	inline void push_up(int p) {
		tree[p].b=(tree[lc].b+tree[rc].b)%mod;
		tree[p].c=(tree[lc].c+tree[rc].c)%mod;
		tree[p].d=(tree[lc].d+tree[rc].d)%mod;
	}
	void build(int &p, int l, int r) {
		p=++on;
		if(l==r) {
			if(1<=l && l<=n) tree[p].b=1, tree[p].c=(-a[l]-a[l+1])%mod, tree[p].d=(ll) a[l]*a[l+1]%mod;
			else tree[p].b=tree[p].c=tree[p].d=0;
		} else build(lc, l, l+r>>1), build(rc, (l+r>>1)+1, r), push_up(p);
	}
	void modify(int lp, int &p, int l, int r, int i) {	//修改 f(x,i) 的式子 
		if(p==lp || !p) p=++on, tree[p]=tree[lp];
		if(l==r) tree[p].b=-tree[p].b, tree[p].c=-tree[p].c, tree[p].d=-tree[p].d;	//取相反数即可 
		else {
			if(i<=(l+r>>1)) modify(tree[lp].son[0], lc, l, l+r>>1, i);
			else modify(tree[lp].son[1], rc, (l+r>>1)+1, r, i);
			push_up(p);
		}
	}
	int query(int p, int l, int r, int x, int y, int z) {
		if(x<=l && r<=y) return ((ll) tree[p].b*z%mod*z+(ll) tree[p].c*z+tree[p].d)%mod;	//即求 bz^2+cz+d 
		return ((lc&&x<=(l+r>>1)?query(lc, l, l+r>>1, x, y, z):0)
		       +(rc&&(l+r>>1)<y?query(rc, (l+r>>1)+1, r, x, y, z):0))%mod;
	}
#undef lc
#undef rc
}
using namespace Segment_Tree;

pair <int, int> tmp[mN];
void getrk() {	//去重，写得有点丑（
	rep(i, 1, n) tmp[i]=make_pair(a[i], i);
	sort(tmp+1, tmp+n+1);
	rep(i, 1, n) {
		if(tmp[i].first!=tmp[i-1].first) ++ork;
		rk[ork]=tmp[i].first, add(ork, tmp[i].second);
	}
}
int main() {
	n=read(), m=read();
	rep(i, 1, n) a[i]=read();
	getrk(), build(rt[0], 0, n);
	rep(i, 1, ork) lfor(t, i) modify(rt[i-1], rt[i], 0, n, ver[t]-1), modify(rt[i-1], rt[i], 0, n, ver[t]);
	//f(x, ver[t]) 和 f(x, ver[t]-1) 在 a[ver[t]] 变化时均需修改
	//因为修改时不想特判 ver[t]==1，所以下标从 0 到 n
	int ans=0, x, l, r;
	while(m--) {
		x=read()^ans, l=read()^ans, r=read()^ans;
		printf("%d\n", ans=(query(rt[upper_bound(rk, rk+ork+1, x)-rk-1], 0, n, l, r-1, x)+mod)%mod);
		//upper_bound-rk-1 找第一个小于等于 x 的数 
	}
	return 0;
}

本人代码常数巨大，欢迎各路神仙吊打。

这里放上 Push_Y 的写法，以供参考。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int gin(){
	int s=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*f;
}

const int N=3e5+5,M=41,mod=1e9+7;
int n,m,idx,len;
int a[N],b[N],rt[N];
int lc[N*M],rc[N*M];
vector<int> pos[N];

struct node{
	int a,b,c;
	inline void qf(){a=-a,b=-b,c=-c;}
	inline int ans(int x){return (a*x%mod*x+b*x%mod+c+mod)%mod;}
}e[N*M];

inline int getid(int x){return lower_bound(b+1,b+len+1,x)-b;}

inline void pushup(int x){
	e[x].a=(e[lc[x]].a+e[rc[x]].a)%mod;
	e[x].b=(e[lc[x]].b+e[rc[x]].b)%mod;
	e[x].c=(e[lc[x]].c+e[rc[x]].c)%mod;
}

int build(int l,int r){
	int x=++idx;
	if(l==r){
		if(l!=0) e[x]=(node){1,(-a[l]-a[l+1])%mod,a[l]*a[l+1]%mod};
		return x;
	}
	int mid=l+r>>1;
	lc[x]=build(l,mid);
	rc[x]=build(mid+1,r);
	pushup(x);
	return x;
}

int upd(int x,int root,int l,int r,int v){
	if(x==root || !x) x=++idx,e[x]=e[root],lc[x]=lc[root],rc[x]=rc[root];
	if(l==r){
		e[x].qf();
		return x;
	}
	int mid=l+r>>1;
	if(v<=mid) lc[x]=upd(lc[x],lc[root],l,mid,v);
	else rc[x]=upd(rc[x],rc[root],mid+1,r,v);
	pushup(x);
	return x;
}

int query(int x,int l,int r,int L,int R,int X){
	if(L<=l && r<=R) return e[x].ans(X);
	int mid=l+r>>1,res=0;
	if(lc[x] && L<=mid) res+=query(lc[x],l,mid,L,R,X);
	if(rc[x] && mid<R ) res+=query(rc[x],mid+1,r,L,R,X);
	return res%mod;
}

signed main(){
	n=gin(),m=gin();
	for(int i=1;i<=n;i++)
		a[i]=b[i]=gin();
	sort(b+1,b+n+1);	
	len=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)
		pos[getid(a[i])].push_back(i);
	rt[1]=build(0,n);
	for(int i=2;i<=len+1;i++)
		for(int j=0;j<pos[i-1].size();j++){
			int v=pos[i-1][j];
			rt[i]=upd(rt[i],rt[i-1],0,n,v-1);
			rt[i]=upd(rt[i],rt[i-1],0,n,v);
		}
	int last=0;
	while(m--){
		int x=gin()^last,l=gin()^last,r=gin()^last;
		last=(query(rt[lower_bound(b+1,b+len+1,x)-b],0,n,l,r-1,x)+mod)%mod;
		printf("%lld\n",last);
	}
	return 0;
}