概括
每次查询一定范围内的点组成的点对中的最优值，而通过一些分析去减少有用点对的数量，这样子的有用点对称为 支配对
T1
策略是将 \(a_i\) 相同的序列取出来单独考虑
固定 \(b_i<b_j,i<j\) 然后考虑能找出来一个序列 \(i,j1,j2,j3...\)
但是发现选 \(i,j2\) 不如选 \(j1,j2\) 更优，所以最终维护的支配对为 \((i,i+1)\) 即可
固定 \(b_i>b_j,i<j\) 时同理
考虑为什么这样的支配对能覆盖所有的查询
考虑一个区间询问 \((l,r)\) 最终取到的答案一定是区间次大值 q 和最大值 p，考虑我们在维护 q 的支配对时，一定能统计到 p，所以就做完了
类似的，支配对的统计也可以理解为所有的子区间询问造成贡献的对的并集
T2
题解
这次我们反着考虑
考虑一次区间查询 \((l,r)\) 能产生贡献的对有哪些
必然是当序列 \((l,r)\) 有序之后所有的 \((i,i+1)\) 都能产生贡献（也即值域上相邻的两项）
所以我们依旧固定 \(a_i<a_j,i<j\) 和 \(a_i>a_j,i<j\) 两种情况进行考虑（这样分类能包含所有的对，稍加考虑一下就行）
单独考虑 \(a_i<a_j,i<j\) 情况：
固定住 \(i\) 找出来能产生贡献的 \(j\) 序列（就是满足 \(a_i>a_{ji},a_{ji}<a_{ji-1}\) 的序列）形如 \(i,j1,j2,j3...\)
然而发现如果 \(a_{j2}-a_i>a_{j1}-a_{j2}\) 那还不如选 \((j1,j2)\) 对优
所以选出来的对还要满足 \(a_{j2}-a_i<a_{j1}-a_{j2}\) 发现每次 \(a_{j}-a_i\) 相比至少减半，所以之多有 \(O(logn)\) 个对，做完了
实现
找支配对的子问题：
每次寻找权值在 \([L,R]\) 范围内的最小位置
开一颗权值线段树维护
统计答案的子问题：
有若干个对 \((l,r)\) 然后若干个询问 \((L,R)\)，要求求满足 \(L<=l,r<=R\) 的对的贡献的最小值
经典二维数点问题，L 一维倒着排序，R 用树状数组维护前缀最小值
注意：
求区间最接近且不相等的两数之差的绝对值。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e9+5,M=1e9;
int n,q,cnt,root;
int a[N],t[N],ans[N];
struct query{int r,i;
};
vector<int>pr[N];
vector<query>qu[N];
struct dot{int ls,rs,mn;
}tr[N*31];
struct tree1{int newnode(){tr[++cnt]={0,0,inf};return cnt;}void update(int k){tr[k].mn=min(tr[tr[k].ls].mn,tr[tr[k].rs].mn);}void add(int &k,int l,int r,int x,int y){if(!k) k=newnode();if(l==r){tr[k].mn=y;return;}int mid=(l+r)>>1;if(x<=mid) add(tr[k].ls,l,mid,x,y);else add(tr[k].rs,mid+1,r,x,y);update(k);}int query(int k,int l,int r,int x,int y){if(!k) return inf;if(x<=l&&r<=y){return tr[k].mn;}int mid=(l+r)>>1,res=inf;if(x<=mid) res=min(res,query(tr[k].ls,l,mid,x,y));if(y>mid) res=min(res,query(tr[k].rs,mid+1,r,x,y));return res;}void clear(){for(int i=1;i<=cnt;i++){tr[i]={0,0,0};}cnt=0;root=0;}
}tree1;
struct tree2{void init(){for(int i=1;i<=n;i++) t[i]=inf;}int lowbit(int x){return x&(-x);}void add(int x,int k){for(;x<=n;x+=lowbit(x)){t[x]=min(t[x],k);}}int query(int x){int res=inf;for(;x;x-=lowbit(x)){res=min(res,t[x]);}return res;}
}tree2;
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}tr[0].mn=inf;//注意update时可能会更新0的答案for(int i=n;i>=1;i--){int l=a[i]+1,r=M;//一定要注意不相等的限制while(1){int num=tree1.query(root,1,M,l,r);if(num==inf) break;pr[i].push_back(num);// printf("%d %d\n",i,num);r=(a[num]+a[i]+1)/2-1;if(r<=a[i]) break;}tree1.add(root,1,M,a[i],i);}tree1.clear();for(int i=n;i>=1;i--){int l=1,r=a[i]-1;while(1){int num=tree1.query(root,1,M,l,r);if(num==inf) break;pr[i].push_back(num);// printf("%d %d\n",i,num);l=(a[num]+a[i])/2+1;if(l>=a[i]) break;}tree1.add(root,1,M,a[i],i);}for(int i=1;i<=q;i++){int l,r;scanf("%d%d",&l,&r);qu[l].push_back({r,i});}tree2.init();for(int i=n;i>=1;i--){for(int j:pr[i]) tree2.add(j,abs(a[i]-a[j]));for(auto j:qu[i]) ans[j.i]=tree2.query(j.r);}for(int i=1;i<=q;i++){printf("%d\n",ans[i]);}
}T3
题解
看见树上距离直接上点分治
一次点分治内部的做法：
每个节点到根都会有一个距离
但是我们似乎无法判掉两个点在同一个子树中的贡献
但是何妨呢，两个点在同一个子树的距离一定大于两个点正常的距离，对答案没有影响
问题转化成了：
在一次点分治内部，每个点都有一个 \(b_i\) 然后需要使得 \(b_i+b_j\) 最小
转化为T1
做法
点分治不多说
然后先让 b 按照下标排序，然后问题转化成了：
找 \(b_i<=b_j,i<j\) 的第一个j，就是找i之后第一个大于i的数
单调栈维护
代码
T4
限制很神秘，但是肯定得通过一些分治什么的技巧简化问题
因为 x 的限制比较复杂，所以分治 y
现在变成了左下有一块，右上有一块，两块中的 x 要满足 \(L<=x_i,x_j<=R\) 或 \(x_i<L<R<x_j\)
就是对于一组询问要么两个 x 都在里，要么都在外
一组不合法情况就是一个 x 在里一个在外
此时只需要调整一个即可
发现 \(w_i+w_j\) 最大的是找到两边的最大值相加是最优的
所以两边的最大值必然有一个在对中
所以维护所有包含最大值的对，一共有 \(O(N)\) 个，可以通过本题
T5
这种题就是猜，猜能拆成 \(i,j\) 分别求贡献的题目
然而事实上也能拆掉
考虑 \(\varphi (p_i\times p_j)\) 和 \(\varphi (p_i)\times \varphi (p_j)\) 之间的关系
考虑到欧拉函数的公式 \(\varphi (x)=x\times \prod (1-\frac{1}{p})\)
然后 \(\varphi (p_i)\times \varphi (p_j)\) 他们就是多乘了 \(p_i\) 和 \(p_j\) 的共同质因数产生的贡献
假设 \(p_i\) 和 \(p_j\) 的值因子集合为 S 和 T，那么 \(\varphi (p_i)\times \varphi (p_j)\) 相当于直接将两个集合加起来，显然，要想求两个集合的并，多算了一个两个集合的交的贡献，所以乘上 \(\frac{\gcd(p_i,p_j)}{\varphi(\gcd(p_i,p_j))}\) 就能消掉交的贡献了
公式：
这样枚举 \(d=\gcd\) 然后将含有当前 \(d\) 的因数的所有元素取出，统计一遍答案，考虑如果 \(d\lt\gcd\) 会不会统计错误，发现它会多乘上几个 \((1-\frac{1}{p})\) 使得答案更小，不会造成影响
但是是 \(O(n^2)\)，需要小小的优化
枚举每个数的因数，然后挂在因数所在的集合内，然后转化为T1
T6
看到这种题还是枚举 \(d=\gcd\)，分解每个数的因数，然后把数挂在上面，做法同上
然后在序列中找到 \(j-i\le k-j\)，显然 \(j=i+1\) 最优，然后双指针找到最近的 \(k\)
复杂度分析一下发现有 \(O(n\sqrt n)\) 个支配对
问题变为有 \(O(n\sqrt n)\) 个 \((l,r)\) 的对，有 \(O(q)\) 个 \((L,R)\) 的查询 \(L\le l,r\le R\)
然后树状树组 \(O(n\sqrt n\log n+n\log n)\) 的，发现复杂度瓶颈在加入
所以考虑复杂度平衡
还是扫描线，但是我 \(O(1)\) 加入， \(O(\sqrt n)\) 分块查询，复杂度平衡了
