给定：
两个长度为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]互不相等
Input
n Q m
A1 A2 ....An
B1 B2 ....Bn
K1 K2 ....Km
l1 r1
l2 r2
.
.
lQ rQ
Output
Q行，每行一个整数表示相对应的答案。
如果找不到这样的两个数则输出0。
Input示例
4 2 2
1 2 3 4
3 2 1 4
1 3
1 4
2 3
Output示例
7
5 思路：
扫描线的思想，对每个询问右边界从小到大排序，因为边界时向右推的，
如果点b[j]+k或b[j]-k得到的数字在b数组中的位置在j的左边(pos为b[j]+k或b[j]-k在b数组中的位置），
题目要求最大的a[i]+a[j]（pos就是倒着推出来的i)，也就是a[pos]+a[j]最大，
我们可以将a[pos]+a[j]的值储存在下标为pos的地方，因为边界是向右走的，只有当pos在j的左边是才可以储存信息；
比如： 当前右边界：r = 5, j = 3,如果pos = 4，如果将值存在pos，当我们查询范围为4-5时，我们就会得到pos=4的值，但是这个是j=3，i=4的值，不能算进去。
如果pos = 2,小于j;我们能查询的区间是x-r(右边界为r），如果我们查询2 - 5，可以得到i=2,j=3的值，
因为对r排序，并且是从小到大走，所以当pos < j时，我们可以把值存在下标为pos的地方，用线段树或树状数组维护下区间的最大值就好了。 实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l+r)>>1
const int M = 1e5+;
int sum[M<<],n,q,m;
int a[M],b[M],id[M],k[],cnt,maxx[M],ans[M];
struct node{
int l,r,id;
}e[M];
bool cmp(node x,node y){
if(x.r == y.r) return x.l < y.l;
else return x.r < y.r;
}
void pushup(int rt){
sum[rt] = max(sum[rt<<],sum[rt<<|]);
}
void update(int p,int c,int l,int r,int rt){
if(l == r){
sum[rt] = max(sum[rt],c);
return ;
}
mid;
if(p <= m) update(p,c,lson);
else update(p,c,rson);
pushup(rt);
} int query(int L,int R ,int l,int r,int rt){
if(L <= l&&R >= r){
return sum[rt];
}
mid;
int ret = ;
if(L <= m) ret = max(ret,query(L,R,lson));
if(R > m) ret = max(ret,query(L,R,rson));
return ret;
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
cin>>n>>q>>m;
for(int i = ;i <= n;i ++) cin>>a[i];
for(int i = ;i <= n;i ++) cin>>b[i],id[b[i]] = i;
for(int i = ;i <= m;i ++) cin>>k[i];
for(int i = ;i <= q;i ++){
cin>>e[i].l>>e[i].r;
e[i].id = i;
}
sort(e+,e++q,cmp);
int l = ;
for(int i = ;i <= q;i ++){
int r = e[i].r;
for(int j = l;j <= r;j ++){
for(int s = ;s <= m;s ++){
int num = b[j] + k[s];
int pos = id[num];
if(num <= n&&pos < j&&a[j] + a[pos] > maxx[pos]){
maxx[pos] = a[j] + a[pos];
update(pos,maxx[pos],,n,);
}
num = b[j] - k[s];
pos = id[num];
if(num >= &&pos < j&&a[j] + a[pos] > maxx[pos]){
maxx[pos] = a[j] + a[pos];
update(pos,maxx[pos],,n,);
}
}
}
ans[e[i].id] = query(e[i].l,e[i].r,,n,);
l = r;
}
for(int i = ;i <= q;i ++) cout<<ans[i]<<endl;
return ;
}