给定：
两个长度为n的数列A 、B
一个有m个元素的集合K
询问Q次
每次询问[l,r]，输出区间内满足|Bi-Bj|∈K 的最大Ai+Aj

数据约定：
n,Q<=100000
m <= 10
0<=A[i]<=1000000000
1<=B[i]<=n
1<=K[i]<=n
保证B[i]互不相等
输入
n Q m
A1 A2 …An
B1 B2 …Bn
K1 K2 …Km
l1 r1
l2 r2
.
.
lQ rQ

输出
Q行，每行一个整数表示相对应的答案。
如果找不到这样的两个数则输出0。
输入样例
4 2 2
1 2 3 4
3 2 1 4
1 3
1 4
2 3
输出样例
7
5

考虑离线之后的做法。我们我们要做的就是把满足关系的放到线段树或者树状数组中。

我们可以注意到，m是很小的，所以我们枚举即可，处理出每个值所在的位置。

然后枚举集合当中每个元素，是否当前的元素组合之后可以等于，然后再把总和ai+aj放到线段树的左端点。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,Q,m,a[N],b[N],pos[N],k[N],res[N];
struct node{int l,r,id;}q[N];
struct seg{int l,r,mx;}t[N<<2];
int cmp(node a,node b){return a.r<b.r;}
inline void push_up(int p){t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;
	if(l==r)	return ; int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
}
void change(int p,int x,int v){
	if(t[p].l==t[p].r)	return void(t[p].mx=max(t[p].mx,v));
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	change(p<<1,x,v);
	else change(p<<1|1,x,v);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].mx;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return max(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));
}
signed main(){
	cin>>n>>Q>>m;
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)	scanf("%lld",&b[i]),pos[b[i]]=i;
	for(int i=1;i<=m;i++)	scanf("%lld",&k[i]);
	for(int i=1;i<=Q;i++)	scanf("%lld %lld",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+1+Q,cmp); build(1,1,n);	int j=1;
	for(int i=1;i<=Q;i++){
		for(;j<=q[i].r;j++){
			for(int s=1;s<=m;s++){
				if(b[j]+k[s]<=n&&pos[b[j]+k[s]]<j)	
					change(1,pos[b[j]+k[s]],a[j]+a[pos[b[j]+k[s]]]);
				if(b[j]-k[s]>=1&&pos[b[j]-k[s]]<j)
					change(1,pos[b[j]-k[s]],a[j]+a[pos[b[j]-k[s]]]);
			}
		}
		res[q[i].id]=ask(1,q[i].l,q[i].r);
	}
	for(int i=1;i<=Q;i++)	cout<<res[i]<<endl;
	return 0;
}