久違的eoj題解
思路來源

題面

單點時限: 3.0 sec
記憶體限制: 512 MB

章魚王沿著國王大道巡視著他強大的王國，國王大道可以被看做一條直線，章魚王的城堡的位置是 0 0 0，

章魚王知道他的國家里有 n n n 個 WiFi 信號發射器，第 i i i 個發射器在 a i a_i ai? 位置，代表章魚王城堡向東 a i a_i ai? 米（若 a i < 0 a_i<0 ai?<0 則為向西），WiFi 的強度為 b i b_i bi?，代表 a i a_i ai? 處能接收到強度為 b i b_i bi? 的信號，而與信號發射器距離每增加 1 1 1 米，信號強度就減少 1 1 1，直到信號為 0 0 0 就不再減少，

章魚王有 q q q 個詢問，他想知道在國王大道 c i c_i ci? 位置處能接收到的最大信號強度，

輸入格式
第一行為資料組數 T ( T ≤ 10 ) T(T\leq 10) T(T≤10) ，

每組資料第一行為 n , q n,q n,q ，第二行為 n n n 個數字 a i a_i ai?，第三行為 n n n 個數字 b i b_i bi?，接下來一行 q q q 個詢問 c i c_i ci?，

保證 40 % 40\% 40% 的資料滿足： 1 ≤ n , q ≤ 1000 1\leq n,q\leq 1000 1≤n,q≤1000，
保證 100 % 100\% 100% 的資料滿足： 1 ≤ n , q ≤ 1 0 5 , 0 ≤ ∣ a i ∣ ≤ 1 0 9 , 0 ≤ b i ≤ 1 0 9 , 0 ≤ ∣ c i ∣ ≤ 1 0 9 1\leq n,q\leq 10^5, 0\leq |a_i|\leq 10^9,0\leq b_i\leq 10^9,0\leq |c_i|\leq 10^9 1≤n,q≤105,0≤∣ai?∣≤109,0≤bi?≤109,0≤∣ci?∣≤109，

所有數均為整數，

輸出格式
對于每組資料中的每個詢問，輸出一行結果，

樣例

思路分析

假設在位置 p o s pos pos 處的WiFi發射器的信號強度為 v a l val val，該WiFi發射器在點 x x x 處的信號強度為 p p p ， 則可得 p = v a l ? ∣ x ? p o s ∣ = { v a l + p o s ? x （ x 左 邊 ） v a l ? p o s + x （ x 右 邊 ） p = val-|x-pos|=\left\{\begin{matrix}val+pos-x （x左邊） \\ val-pos+x（x右邊）\end{matrix}\right. p=val?∣x?pos∣={val+pos?x（x左邊）val?pos+x（x右邊）?
要求得 p p p 的最大值，即找到 x x x 左邊 v a l + p o s val+pos val+pos 的最大值和 x x x 右邊 v a l ? p o s val-pos val?pos 的最大值，由于資料規模大，用順序查找暴搜必然超時，所以采用二分查找，

對于 x x x左邊的WiFi發射器，有 x ? p o s ≥ 0 x-pos \geq 0 x?pos≥0， p = v a l ? x + p o s p = val - x + pos p=val?x+pos ，那么我們只需二分查找找到 x ≥ p o s x \geq pos x≥pos的點在按 ( v a l + p o s ) (val+pos) (val+pos)鍵值排序的最后一個符合 x ≥ p o s x \geq pos x≥pos的Wifi發射器
同理，對于 x x x右邊， x ? p o s < 0 x-pos < 0 x?pos<0， p = v a l + x ? p o s p = val + x - pos p=val+x?pos，二分查找找到 x < p o s x < pos x<pos的點在按 ( v a l ? p o s ) (val-pos) (val?pos)鍵值排序的最后一個符合 x < p o s x < pos x<pos 的Wifi發射器

但是當我們按照 v a l ? p o s val-pos val?pos 或者 v a l + p o s val + pos val+pos 排序之后， p o s pos pos本身在陣列中不一定是單調的，我們知道二分的前提是單調性，于是利用單調佇列，在不影響原陣列的順序的情況下，處理出 p o s pos pos的單調性，

ac代碼

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int pos,val;
};

bool cmp(node a,node b)
{
	if(a.pos + a.val != b.pos + b.val)
		return a.pos + a.val < b.pos + b.val;
	return a.pos > b.pos; 
}

bool cmp1(node a,node b)
{
	if (a.val - a.pos != b.val - b.pos)
		return a.val - a.pos < b.val - b.pos;
	return a.pos < b.pos;
}

int n,q;

int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> q;
		node info[n], info1[n];
		for(int i=0;i<n;i++)
		{
			cin >> info[i].pos;
			info1[i].pos=info[i].pos;
		}
		for(int i=0;i<n;i++)
		{
			cin >> info[i].val;
			info1[i].val=info[i].val;
		}
		//按照x左右不同鍵值排序
		sort(info,info+n,cmp);
		sort(info1,info1+n,cmp1);
		
		//單調佇列，left中的pos遞增，right中pos遞減，兩個佇列中鍵值都是遞增
		vector<node> left,right;
		left.push_back(info[0]);
		right.push_back(info1[0]);
		for(int i=1;i<n;i++)
		{
			int rear=left.size()-1;
			if(info[i].pos > left[rear].pos)
			{
				left.push_back(info[i]);
				continue;
			}
			else if(info[i].pos < left[rear].pos)
			{
				//pos更小更易滿足條件 x >= my[i].pos，且由于已經排序了p1會更大
				while(left.size()&&info[i].pos<left[left.size()-1].pos)
					left.pop_back();
				left.push_back(info[i]);
			}
		}
		
		for(int i=1;i<n;i++)
		{
			int rear=right.size()-1;
			if(info1[i].pos < right[rear].pos)
			{
				right.push_back(info1[i]);
				continue;
			}
			else if(info1[i].pos > right[rear].pos)
			{
				//pos更大更易滿足條件 x < my[i].pos，且由于已經排序了p2會更大
				while(right.size()&&info1[i].pos>right[right.size()-1].pos)
					right.pop_back();
				right.push_back(info1[i]);
			}
		}
		
		int c;
		while(q--) 
		{
			cin >> c;
			int p1=0,p2=0;
			
			//二分查找
			int l,r;
			l=0,r=left.size()-1;
			while(l < r)
			{
				int mid = (l+r+1)>>1;
				if(left[mid].pos<=c)
					l=mid;
				else
					r=mid-1;
			}
			if(left[l].pos<=c)
				p1=max(0,left[l].pos+left[l].val-c);
				
			l=0,r=right.size()-1;
			while(l < r)
			{
				int mid = (l+r+1)>>1;
				if(right[mid].pos>c)
					l=mid;
				else
					r=mid-1;
			}
			if(right[l].pos>c)
				p2=max(0,right[l].val-right[l].pos+c);
				
			cout << max(p1,p2) << endl;
		} 
	}
}