传送门

欢迎踩博客

前置知识：

SA 数组。

题意：

• 给出 $n$ 个在 $[1,n]$ 内的数 $a_i$。

• $q$ 次询问，每次给出 $s,l,r$，问是否 $\exists b\in[1,n]$ 使 $\forall k\in[0,r-l]$，$a_{l+k}+a_{b+k}=s$。

• $n,q\le4\times10^5$。

为叙述方便，设以 $s$ 的第 $i$ 个元素为首个元素的后缀为 $\operatorname{suff}(s,i)$。

分析：

• Subtask 0：$n,q\le500$。

暴力枚举每一个 $b$ 进行判断。

• Subtask 1：$n,q\le8\times10^3$。

是 $O(nq)$ 的 KMP 写法，并不是正解。

对于每一个询问，设 $c_k=s-a_{l+k}$（$k\in[0,r-l]$），那么如果存在 $b$ 满足 $a_{b+k}=c_k$，就满足条件，否则不满足。

原问题转换成了能否在 $a$ 中找到一个子串和 $c$ 相同，可以用 KMP 解决。这个过程是 $O(n)$ 的，$q$ 次询问就是 $O(nq)$。

这个 Subtask 虽然和正解使用的算法不同，但对思路有一定帮助。

• Subtask 2：$s$ 相同。

若 $s$ 相同，就说明 $s-a_i$ 相同。所以每次得出的 $c$ 是另一个串 $d$（$d_i=s-a_i$） 的子串。问题转换成求 $d$ 的一个子串是否在 $a$ 中出现过。

对 $d$ 和 $a$ 一起求 SA，假设询问的 $d$ 的子串是 $d_l,d_{l+1},\dots,d_r$，那么只需要判断 $\operatorname{suff}(d,l)$ 与 $a$ 的所有后缀的 lcp 的最大值是否不小于 $r-l+1$ 即可。

可以二分求以 $l$ 开始的后缀在 rank 中的前驱和后继，复杂度 $O((n+q)\log n)$，已经能过了。

• Subtask 3：无限制。

注意到 $a_{l+k}+a_{b+k}=s$，$a_{l+k+1}+a_{b+k+1}=s$ 可以推出 $(a_{l+k+1}-a_{l+k})+(a_{b+k+1}-a_{b+k})=0$，即差分数组是相反数。

求出差分数组 $a'$ 以及差分的相反数数组 $d'$。问题等价于求所有满足 $a_b+a_l=s$ 的 $\operatorname{suff}(d',b)$ 和 $\operatorname{suff}(a',l)$ 的最长公共前缀的最大值是否不小于 $r-l$。

以样例为例，各数组如下表：

对于询问三，$\operatorname{suff}(a',l)=\{-2,-1\}$。

满足 $a_b+a_l=s$ 的 $b$ 有 $1$，$2$，$6$。所有 $\operatorname{suff}(d',b)$ 为：$\operatorname{suff}(d',1)=\{0,-2,-1,2,1\}$，$\operatorname{suff}(d',2)=\{-2,-1,2,1\}$，$\operatorname{suff}(d',6)=\{\}$。

其中 $\operatorname{suff}(d',2)$ 与 $\operatorname{suff}(a',4)$ 的公共前缀长度为 $2$。这意味着 $a'_2+a'_4=0$，$a'_3+a'_5=0$，并且由于因为已经保证了 $a_2+a_4=s$，所以：

$a_3+a_5=(a_2+a'_2)+(a_4+a'_4)=s$，$a_4+a_6=(a_3+a'_3)+(a_5+a'_5)=s$，满足条件。

注意到所有 $a_b+a_l=s$ 的 $a_b$ 是相同的废话，所以可以对于每一个 $v$，将所有 $a_b=v$ 的 $b$ 放在一个数组里，按 rank 排序，询问时二分 $\operatorname{suff}(a',l)$ 的 rank 在哪个位置即可。

思路：

• 求出差分数组与差分的相反数数组。

• 对于每一个询问，求出 $\max\limits_{a_b+a_l=s}\{\operatorname{lcp}(\operatorname{suff}(a',l),\operatorname{suff}(d',b))\}$ 是否不小于 $r-l$。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l; i<=r; ++i)
#define rrep(i, r, l) for(int i=r; i>=l; --i)
#define ll long long
#define il inline
#pragma GCC diagnostic ignored "-Wparentheses"
using namespace std;
const int mN=4e5+100, mM=2*mN, mD=21;
il int read() {
	int res=0; char c=getchar(); while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9') res=(res<<1)+(res<<3)+(c^48), c=getchar(); return res;
}
il int max_(int a, int b) {return a>b? a: b;}
il int min_(int a, int b) {return a<b? a: b;}
int n, q, m, a[mN], lg[mM], mn[mD][mM], f[mN], fl[mN], fr[mN];
int c[mM];
il int cal_min(int l, int r) {return min(mn[lg[r-l+1]][l], mn[lg[r-l+1]][r-(1<<lg[r-l+1])+1]);}

//begin 板子
int ork, rk[2][mM*2], rak[mM], sa[mM], lcp[mM], buc[mM], tmp1[mM], tmp2[mM]; 
il void get_buc(int *a) {
	rep(i, 0, ork) buc[i]=0;
	rep(i, 1, m) ++buc[a[i]];
	rep(i, 1, ork) buc[i]+=buc[i-1];
}
void get_sa() {
	rep(i, 1, m) rk[0][i]=c[i];
	int t=0; ork=m;
	for(; t<=lg[m]; ++t) {
		get_buc(rk[t&1]+(1<<t));
		rep(i, 1, m) tmp1[buc[rk[t&1][i+(1<<t)]]--]=i;
		get_buc(rk[t&1]);
		rrep(i, m, 1) tmp2[buc[rk[t&1][tmp1[i]]]--]=tmp1[i];
		ork=0;
		rep(i, 1, m) {
			if(rk[t&1][tmp2[i]]!=rk[t&1][tmp2[i-1]] || rk[t&1][tmp2[i]+(1<<t)]!=rk[t&1][tmp2[i-1]+(1<<t)]) ++ork;
			rk[t&1^1][tmp2[i]]=ork;
		}
		if(ork==m) {++t; break;}
	}
	rep(i, 1, m) sa[rak[i]=rk[t&1][i]]=i;
}
#define j lcp[rak[i]]
il void get_lcp() {rep(i, 1, m) for(j=max_(lcp[rak[i-1]]-1, 0); c[i+j]==c[sa[rak[i]+1]+j]; ++j);}
#undef j
//end 板子 

il bool sol(int s, int l, int r) {	//处理询问 (s,l,r) 
	int v=s-a[l], L=fl[v], R=fr[v];
	if(v<=0 || v>n || fl[v]>fr[v]) return 0;	//没有 a[i]=v, 直接返回 
	while(L<=R) if(f[L+R>>1]<rak[l]) L=(L+R>>1)+1; else R=(L+R>>1)-1;	//二分 rak[l] 的位置 
	//二分的结果满足 f[R]<rak[l]<f[L] 
	return max_(fl[v]<=R? cal_min(f[R], rak[l]-1): 0, L<=fr[v]? cal_min(rak[l], f[L]-1): 0)>=r-l;
	//如果在范围内就求 lcp，否则为 0 
}
int main() {
	n=read(), q=read(), m=2*n;
	rep(i, 2, m) lg[i]=lg[i>>1]+1;
	rep(i, 1, n) a[i]=read();
	rep(i, 1, n-1) c[i]=a[i+1]-a[i]+n+1, c[i+n]=a[i]-a[i+1]+n+1;	//c[1]~c[n] 为 a', c[n+1]~c[2n] 为 d' 
	c[n]=c[m]=1;
	get_sa(), get_lcp();	//SA
	rep(i, 1, m) mn[0][i]=lcp[i];
	rep(t, 1, lg[m]) rep(i, 1, m-(1<<t)+1) mn[t][i]=min_(mn[t-1][i], mn[t-1][i+(1<<t-1)]);	//ST

	rep(i, 0, n) buc[i]=0;
	rep(i, 1, n) ++buc[a[i]];
	rep(i, 1, n) buc[i]+=buc[i-1];
	rep(i, 1, n) fl[i]=buc[i-1]+1, fr[i]=buc[i];	//值为 v 的 a[i] 在 fl[v] 到 fr[v] 的范围内 
	rep(i, 1, n) f[buc[a[i]]--]=rak[i+n];	//把 a[i]=v 的 rank[d'[i]] 放进 f[fl[v]~fr[v]] 
	rep(i, 1, n) if(fl[i]<=fr[i]) sort(f+fl[i], f+fr[i]+1);
	int s, l, r;
	do s=read(), l=read(), r=read(), puts(sol(s, l, r)? "Yes": "No"); while(--q);
	return 0;
}

特别申明：本题解为团队成员 ATue 所写。